time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 employee n. 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
output
D
input
6
DDRRRR
output
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.
【题目链接】:http://codeforces.com/contest/749/problem/C
【题解】
对于一个人来说；它肯定要让一个竞争者出局;
但是让哪一个人出局都是让对手-1；
但是如果让你后面的对手出局。这样对方就少了一次让己方出局的机会.
这样显然对己方有利
所以每次让人出局的时候、优先检索你后方的人（对手);
(只要是你后方的人就可以了，所以你可以不用multiset,直接记录一下对手、最后一个人的位置,然后直接删掉这个人);
(如果对手集合为空，你就赢了,删掉这个人的话,你可以用数组模拟链表，而不用multiset);
如果没有就在前方也找一下;
如果都没有，就这个人赢;
否则让那个人出局;
这些操作都能用multiset实现。
当然完全没必要用multiset;
有了上面的思路其实很容易写出其他程序了;
(程序中的h起到的其实就是链表的作用,t的话则是检索大于某个位置的0或1是否存在(D和R))
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int MAXN = 1e6+10;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const char d[2] = {'D','R'};
const double pi = acos(-1.0);
struct rec{
int pos,x;
friend bool operator < (rec a,rec b)
{
return a.pos < b.pos;
}
};
multiset<rec>h;
struct rec2{
int pos,x;
friend bool operator < (rec2 a,rec2 b)
{
if (a.x==b.x)
return a.pos < b.pos;
else
return a.x < b.x;
}
};
multiset<rec2>t;
int n,c0,c1;
char s[209999];
int main()
{
//freopen("F:\rush.txt","r",stdin);
rei(n);
scanf("%s",s+1);
rep1(i,1,n)
{
if (s[i]=='D')
h.insert({i,0}),t.insert({i,0});
else
h.insert({i,1}),t.insert({i,1});
}
while (!h.empty())
{
__typeof(h.begin()) it = h.begin(),tpos;
__typeof(t.begin()) pos;
while (it != h.end())
{
rec te = (*it);
pos = t.upper_bound({te.pos,1-te.x});
rec2 a = (*pos);
if (a.x==te.x)
pos = t.upper_bound({0,1-te.x});
a = (*pos);
if (a.x!=1-te.x)
{
putchar(d[te.x]);
return 0;
}
t.erase(pos);
tpos = h.lower_bound({a.pos,a.x});
rec dd = (*tpos);
h.erase(tpos);
it++;
}
}
return 0;
}