Voting「建议收藏」_IT分享知识网

大家好，欢迎来到IT知识分享网。

There are n employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote.

Each of the employees belongs to one of two fractions: depublicans or remocrats, and these two fractions have opposite opinions on what should be the outcome of the vote. The voting procedure is rather complicated:

Each of n employees makes a statement. They make statements one by one starting from employees 1 and finishing with employeen. If at the moment when it’s time for the i-th employee to make a statement he no longer has the right to vote, he just skips his turn (and no longer takes part in this voting).
When employee makes a statement, he can do nothing or declare that one of the other employees no longer has a right to vote. It’s allowed to deny from voting people who already made the statement or people who are only waiting to do so. If someone is denied from voting he no longer participates in the voting till the very end.
When all employees are done with their statements, the procedure repeats: again, each employees starting from 1 and finishing with n who are still eligible to vote make their statements.
The process repeats until there is only one employee eligible to vote remaining and he determines the outcome of the whole voting. Of course, he votes for the decision suitable for his fraction.

You know the order employees are going to vote and that they behave optimal (and they also know the order and who belongs to which fraction). Predict the outcome of the vote.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of employees.

The next line contains n characters. The i-th character is ‘D’ if the i-th employee is from depublicans fraction or ‘R’ if he is from remocrats.

Output

Print ‘D’ if the outcome of the vote will be suitable for depublicans and ‘R’ if remocrats will win.

Examples

input

5
DDRRR

IT知识分享网

output

IT知识分享网D

input

6
DDRRRR

output

IT知识分享网R

Note

Consider one of the voting scenarios for the first sample:

Employee 1 denies employee 5 to vote.
Employee 2 denies employee 3 to vote.
Employee 3 has no right to vote and skips his turn (he was denied by employee 2).
Employee 4 denies employee 2 to vote.
Employee 5 has no right to vote and skips his turn (he was denied by employee 1).
Employee 1 denies employee 4.
Only employee 1 now has the right to vote so the voting ends with the victory of depublicans.

分析：贪心，到某个人时，他必定是删除下一个会出现的对方，因为这样后面己方才能存活；

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, ls[rt]
#define Rson mid+1, R, rs[rt]
#define sys system("pause")
#define intxt freopen("in.txt","r",stdin)
const int maxn=2e5+10;
using namespace std;
ll gcd(ll p,ll q){
     
     return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){
    
    if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
const int dis[][2]={
    
    1,0,0,1,-1,0,0,-1};
inline ll read()
{
    ll x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
    
    if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,k,t,cnt1,cnt2,tmp1,tmp2;
char a[maxn];
set<int>pos;
vi tmp;
int main()
{
    int i,j;
    scanf("%d%s",&n,a);
    rep(i,0,n-1)
    {
        if(a[i]=='D')cnt1++;
        else cnt2++;
        pos.insert(i);
    }
    while(cnt1&&cnt2)
    {
        tmp.clear();
        for(int x:pos)
        {
            if(a[x]=='D')
            {
                if(tmp2)tmp.pb(x),tmp2--,cnt1--;
                else tmp1++;
            }
            else
            {
                if(tmp1)tmp.pb(x),cnt2--,tmp1--;
                else tmp2++;
            }
            if(!cnt1||!cnt2)break;
        }
        for(int x:tmp)pos.erase(x);
    }
    cout<<a[*pos.begin()]<<endl;
    //system("Pause");
    return 0;
}

转载于:https://www.cnblogs.com/dyzll/p/6213199.html

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/7549.html

Voting「建议收藏」

相关推荐

发表回复