题目链接

http://codeforces.com/contest/1154/problem/E

题目思路

首先结构体保存队列信息，并进行排序，flag[]记录队伍

第一种：利用并查集优化，利用一个pre[p]{int r，int l}，来记录位置p左边，和右边下一个可以选的人是谁，

然后选人的时候，就让当前pre[p]指向p+1 or p-1，然后在pre_find中优化并查集

第二种：利用map<int,int>,key-位置p,value-skills,value理论上是没什么用的，然后通过迭代器删减操作，选人删人

这个迭代器可太难了

STL中的容器按存储方式分为两类：一类是序列容器（如：vector，deque），另一类是关联容器（如：list，map，set）。

在使用erase方法删除元素时，有几点需要注意：

1） 对于关联容器（如map， set，multimap，multiset），删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响。

2）对于序列式容器（如vector，deque），删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor，deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置。还好erase方法可以返回下一个有效的iterator。

3）对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种正确的方法都可以使用。

栗子1：（vector）
1
2
3
4
5
6
7
for(auto iter = v.begin(), iter!=v.end(); /*iter++*/)
 {
      if(iter == 3)
           iter = v.erase(iter);
       else
           iter++;
 }
栗子2：（map）
1
2
3
4
5
6
7
8
9
10
11
for(auto iter1 = theMap.begin(); iter1 != theMap.end(); )  
{  
    if(iter1->second == xxx)  
    {  
        theMap.erase(iter1++);  
    }  
    else  
    {  
        ++iter1;  
    }  
}

迭代器传送门

first

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <string>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#define LL long long
using namespace std;
const int MAX = 200020;
const int INF = 0xfffffff;//268435455,2e8;
const double EPS = 0.0000001;
const int MOD = 100;
int T,N,M;


/*-------------------------------------------------------------------------------------------*/
int flag[MAX];
int skill[MAX];
struct STU
{
    int v;
    int p;
}stu[MAX];

struct RL
{
    int l;
    int r;
}pre[MAX];

bool Cmp(STU a,STU b)
{
    return a.v > b.v;
}

/* ------------------------------------------------------------------------------------------*/

int find_prel(int x)
{
    if(pre[x].l == x)
    {
        return x;
    }
    else return pre[x].l = find_prel(pre[x].l);
}

int find_prer(int x)
{
    if(pre[x].r == x)
    {
        return x;
    }
    else return pre[x].r = find_prer(pre[x].r);
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> N >>M;
    int cnt = 0;
    for(int i = 0;i < N;i++)
    {
        cin >> skill[i];
        stu[i].v = skill[i];
        stu[i].p = i;
        pre[i].l = pre[i].r = i;
    }
    sort(stu,stu+N,Cmp);


    int ff = 1;
    for(int i = 0;i < N;i++)
    {
        if(cnt == N) break;
        int x = stu[i].p;
        if(!flag[x])
        {
            flag[x] = ff;
            int cnnt = 0;
            int m;
            for(m = x+1;m < N;m++)
            {
                if(cnnt == M) break;//end flag
                int k = m;
                if(pre[m].r != m)
                {
                    m = find_prer(m);
                }
                if(m == N) break;
                if(!flag[m])
                {
                    flag[m] = ff;
                    cnnt++;
                    cnt++;
                    pre[k].r = min(m+1,N-1);
                    pre[k].l = x;
                }
            }
            pre[x].r = min(m,N-1);

            cnnt = 0;
            for(m = x-1;m >= 0;m--)
            {
                if(cnnt == M) break;
                int k = m;
                if(pre[m].l != m)
                {
                    m = find_prel(m);
                }
                if(m < 0) break;
                if(!flag[m])
                {
                    flag[m] = ff;
                    cnnt++;
                    cnt++;
                    pre[k].l = max(m-1,0);
                    pre[k].r = x;
                }
            }
            pre[x].l = max(m,0);
            if(ff == 1)
            {
                ff = 2;
            }
            else ff = 1;
        }

    }
    for(int i = 0;i < N;i++)
    {
        cout << flag[i];
    }
    return 0;
}

second

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <string>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#define LL long long
using namespace std;
const int MAX = 200020;
const int INF = 0xfffffff;//268435455,2e8;
const double EPS = 0.0000001;
const int MOD = 100;
int T,N,M;


/*-------------------------------------------------------------------------------------------*/
int flag[MAX];//标记队伍
struct STU
{
    int v;
    int p;
}stu[MAX];//对技能值排序


bool Cmp(STU a,STU b)
{
    return a.v > b.v;
}

map<int,int> sk;//保存原始队列key-坐标，value-技能
//这里value好像没什么用，我只是想快速找到坐标在哪

/* ------------------------------------------------------------------------------------------*/


int main()
{
    std::ios::sync_with_stdio(false);
    cin >> N >>M;
    int cnt = 0;
    for(int i = 1;i <= N;i++)
    {
        int x;
        cin >> x;
        stu[i].v = x;
        stu[i].p = i;
        sk[i] = x;
    }
    sort(stu+1,stu+N+1,Cmp);
    int ff = 1;
    for(int i = 1;i <= N;i++)
    {
        map<int,int> ::iterator it;
        int x = stu[i].p;
        if(!flag[x])
        {
            flag[x] = ff;
            //cout << x << " " << ff <<endl;
            int cnnt = 0;
            it = sk.find(x);
            it++;
            while(cnnt != M)//啊啊啊啊啊，这个迭代器操作可太难了
            {
                if(it == sk.end()) break;
                flag[it->first] = ff;
               // cout << it->first << " " << ff <<endl;
                sk.erase(it++);
                cnnt++;
            }
            it = sk.find(x);
            if(it == sk.begin())
            {
                if(ff == 1)
                {
                    ff = 2;
                }
                else ff = 1;
                sk.erase(it);
                continue;
            }
            else it--;
            cnnt = 0;
            while(cnnt != M)
            {
                flag[it->first] = ff;
                //cout << it->first << " " << ff<<endl;
                if(it == sk.begin())
                {
                    sk.erase(it);
                    break;
                }
                else sk.erase(it--);
                cnnt++;
            }
            sk.erase(sk.find(x));
            if(ff == 1)
            {
                ff = 2;
            }
            else ff = 1;
        }

    }
    for(int i = 1;i <= N;i++)
    {
        cout << flag[i];
    }
    return 0;
}