Voting
Time Limit: 1 Sec Memory Limit: 256 MB
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.

传送门:CF749C

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.

Sample Input

1
2
5
DDRRR

Sample Output

1
D

题解

显然最优策略是每次把在自己后面的第一个敌人否决掉 那就建两个队列 第一个队列保存投D的下标 第二个队列保存投R的下标 这样就记录了投票人的优先级 然后开始循环,条件是两个均不为空 先看两个队列的头部,如果D比R小,那么就把R的头部弹出。然后D的头部弹出,加上n后放入D队列的尾部/*重要*/,反之亦然。 最后哪个队列没有空就是赢的队伍
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.io.*;  
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
sc.nextLine();
String s=sc.nextLine();
LinkedBlockingQueue<Integer>queueD=new LinkedBlockingQueue<Integer>();
LinkedBlockingQueue<Integer>queueR=new LinkedBlockingQueue<Integer>();
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='D'){
queueD.add(i); //存入下标
}
else
queueR.add(i);
}
while(!queueR.isEmpty()&&!queueD.isEmpty()){
if(queueR.peek()<queueD.peek()){
int cur=queueR.poll();
queueR.add(cur+n); //+n保持队列优先度的一致性,不加的话会乱掉
queueD.poll();
}
else{
int cur=queueD.poll();
queueD.add(cur+n); //同上
queueR.poll();
}
}
if(queueR.isEmpty()){
System.out.println('D');
}
else
System.out.println('R');
}

}
}