获取中...

-

Just a minute...

更新于 cf 并查集 迭代器 热度 1 喜欢 0

题目链接

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;
}
相关文章
评论
分享
返回顶部
  • ECF-70-2

    八月 9日, 2019

    Educational Codeforces Round 70 (Rated for Div. 2)A.You Are Given Two Binary Strings乘2^k次，其实就是把二进制左移了k位 加法就是对应位加就好了，然...

    ECF-70-2
  • CF-577-2

    八月 7日, 2019

    Codeforces Round #577 (Div. 2)A.Important Exam问学生分数总和最大为多少 那么就是每道题选的最多的选项为答案，计算即可 B.Zero Array如果sum是奇数的一定不行 如果是偶数的话就看...

    CF-577-2
  • CF-569-2

    八月 1日, 2019

    吹爆这一场，第一次打到这么前，虽然赛后打得 Codeforces Round #569 (Div. 2)A.Alex and a Rhombus每次增多（i-1）*4个 B.Nick and Array他的操作真正的意思就是，变负数绝...

    CF-569-2
  • CF-576-2

    七月 31日, 2019

    Codeforces Round #576 (Div. 2)A.City Day啊，爆哭，还想着怎么能优化一下，感觉会超时 结果优化wa了，真好，那就纯暴力 对每一个a，都找到l,r判断区间符不符合条件 注意0天的时候就好 B.Wat...

    CF-576-2
  • ECF-69-2

    七月 30日, 2019

    Educational Codeforces Round 69 (Rated for Div. 2)A.DIY Wooden Ladder找最长的的俩个，然后看是能放的木板多，还是给的木板多 B.Pillars观察发现这个序列有三种情...

    ECF-69-2
  • CF-575-3

    七月 25日, 2019

    Codeforces Round #575 (Div. 3)A.Three Piles of Candies傻逼题，一人拿一堆，剩下一堆还能随便分，加起来除2 B.Odd Sum Segments一个序列里只有奇数个奇数时和才是奇数 ...

    CF-575-3
  • CF-574-2

    七月 19日, 2019

    Codeforces Round #574 (Div. 2)A.Drinks Choosing就把可以凑对的凑在一起，不能的俩俩组合 B.Sport Mafia题目思路：算出全放糖果的sum，算出与留下糖果的差cha 可知，每少放一次...

    CF-574-2
  • CF-571-2

    七月 17日, 2019

    Codeforces Round #571 (Div. 2)Vus the Cossack and a Contestm,k都不小于n Vus the Cossack and Strings通过观察可以发现当字符串中’1’的数量奇偶相...

    CF-571-2
  • ECF-68-2

    七月 15日, 2019

    Educational Codeforces Round 68 (Rated for Div. 2)Remove a Progression找到规律，隔一个删一个 Yet Another Crosses Problem这个气死了，存的...

    ECF-68-2
  • CF-559-2（未完待续）

    七月 14日, 2019

    就学了一个lower把，先放在这里 还要学习读题23333 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748...

    CF-559-2（未完待续）
Please check the parameter of comment in config.yml of hexo-theme-Annie!
ESC