Codeforces Round #388 (Div. 2) - C

题目链接：http://codeforces.com/contest/749/problem/C

题意：给定一个长度为n的D/R序列，代表每个人的派别，然后进行发表意见，顺序是从1到n。每个人到他的回合可以踢掉一个人。被踢掉的人不能参与发表直接跳过他的回合。如此知道剩下一个人。输出那个人所在的派别。

思路：明显的贪心题。为了让同派别的尽可能的留下来，所以应当踢掉在他后面的并且离他最近的其他派别的人。这样后面同派别的人才能发表。如果后面不存在其他派别的人，则应该踢掉前面离他最远的其他派别的人(应该离他最远的下一轮会是先手)。 然后就是按照思路模拟了。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<stdio.h>

#include<queue>

#include<vector>

#include<stack>

#include<map>

#include<set>

#include<time.h>

#include<cmath>

using namespace std;

typedef long long int LL;

const int MAXN =  + ;

char str[MAXN];

int main(){

//#ifdef kirito

//    freopen("in.txt", "r", stdin);

//    freopen("out.txt", "w", stdout);

//#endif

//    int start = clock();

    int n;

    while (scanf("%d", &n) != EOF){

        scanf("%d", &n); scanf("%s", str);

        set<int> D, R;  int totD = , totR = ;

        for (int i = ; i < n; i++){

            if (str[i] == 'D'){ D.insert(i); totD++; }

            else{ R.insert(i); totR++; }

        }

        while (totR&&totD){

            set<int>::iterator it;

            for (int i = ; i < n&&totR&&totD; i++){

                if (str[i] == '#'){ continue; } //已经被vote

                if (str[i] == 'D'){

                    it = R.upper_bound(i); //找到后面理他最近的人

                    if (it == R.end()){ //后面没有，则找前面第一个还在的

                        it = R.begin();

                    }

                    str[*it] = '#'; R.erase(it);

                    totR--;

                }

                else{

                    it = D.upper_bound(i);

                    if (it == D.end()){

                        it = D.begin();

                    }

                    str[*it] = '#'; D.erase(it);

                    totD--;

                }

            }

        }

        printf("%c\n", totD ? 'D' : 'R');

    }

//#ifdef LOCAL_TIME

//    cout << "[Finished in " << clock() - start << " ms]" << endl;

//#endif

    return ;

}