codeforces B. Online Meeting 解题报告

题目链接：http://codeforces.com/problemset/problem/420/B

题目意思：给出一段连续的消息记录：记录着哪些人上线或者下线。问通过给出的序列，找出可能为leader的人的编号。符合leader的条件是：至少有一个人上线的时候，绝对要有该人（leader）的存在。

整个五一都把时间耗在这题里了......首先太感谢jhf大神，竟然可以这么有耐心的跟我这个陌生人讨论题目。但是，限于本人理解能力有点问题，在参考他写的代码里，还是有一些部分不太理解。

以下结合我的理解来说。首先，将有可能为leader的人分成两批：没有在序列中出现过的 + 在序列中有可能是leader的候选人。要知道记录里没有出现过的人都有可能是leader。然后，对于候选人又分成两批：整个记录中的第一人 + 记录中的某一个人。对于记录中第一个人为leader的情况有两种：（1）整个记录里只有上线的人，没有下线的；（2）整个记录里每个人第一次出现都是以上线形式出现，但记录中存在下线。这个时候最有可能为leader 的非第一个人莫属了。对于有可能是记录中的某一个人（有可能不是第一个），需要符合：这些候选人第一次出现以下线形式出现。

那总体的思路就是：挑出候选人，然后在候选人当中选出最后下线的，就是说，上线的人要在该人离开前都要下线。然后加上未出现过的人，就是答案了。

补充：终于找到他的原话 + 我的补充了：

jhf:

1、先预处理，例如+1 -2 补充完整为： +2+1-2-1 这两个是等价的（因为所有的人都是先上线再下线）。实质上就是把直接下线而没有先上线的人的上线记录加在前面，例如-2+3-3-4-1，2 4 1直接下线了，他们是唯一有可能当leader的，然后试图从中再筛选，筛选的方法就是看这些人有没有中途在还有人在线的时候就下线了

2、然后遍历记录每走一条，淘汰那些不符合的人...

最终版：

x第一次出现是-x的形式的列为候选

如果没有这种的，把记录中的第一个数列为候选

然后开始进一步筛选

筛选就看这些候选中有没有在有人在线的情况下下线的

如果有就排除

然后加上那些没在记录中出现过得人就是答案

...

候选人在有人在线的情况下下线了

答：

用一个bool数组标记出候选人

用一个int记录当前在线人数

查bool数组判断他是不是候选人，再看在线人数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int MAX_MSG = 1e5 + 2;
 8 const int MAX_PEOPLE = 1e5 + 2;
 9 int people, msg, init_num;
10 int ans[MAX_PEOPLE];
11 bool vis[MAX_PEOPLE], wait[MAX_PEOPLE];     // vis[]: 针对整个记录中没有出现过的人；wait[]：记录第一次出现是离线的人的编号
12 
13 struct node
14 {
15     int id;
16     bool on;
17 }user[MAX_MSG];
18 
19 void Input()
20 {
21     char ch;
22     scanf("%d%d", &people, &msg);
23     for (int i = 1; i <= msg; i++)
24     {
25         cin >> ch >> user[i].id;
26         user[i].on = (ch == '+');   // 代表该人第一次出现是上线的
27     }
28 }
29 
30 void Make_wait()     // 挑出候选人
31 {
32     memset(vis, 0, sizeof(vis));
33     memset(wait, 0, sizeof(wait));
34     bool did = false;
35     init_num = 0;
36     for (int i = 1; i <= msg; i++)
37     {
38         if (vis[user[i].id])
39             continue;
40         if (!user[i].on)
41         {
42             did = true;
43             init_num++;     // 统计第一次出现是下线的人的数量
44             wait[user[i].id] = true;
45         }
46         vis[user[i].id] = true;
47     }
48     if (!did)     // 候选人只有记录中的第一个人(不考虑!vis[])
49         wait[user[1].id] = true;
50 }
51 
52 void Work()  // 判断候选人
53 {
54     int on_num = init_num;   // 第一次出现是以下线方式出现的人，即候选人
55     for (int i = 1; i <= msg; i++)
56     {
57         if (user[i].on)
58         {
59             on_num++;                 
60             if (on_num == 1 && !wait[user[i].id])   // 这条语句令我十分不解，可能是代表候选人是记录中的第一个人
61             {
62                 memset(wait, 0, sizeof(wait));
63             }
64             continue;
65         }
66         on_num--;          
67         if (!wait[user[i].id])     // 非候选人直接跳过
68             continue;
69         if (on_num > 0)            // 离线对应该人不是leader
70             wait[user[i].id] = false;
71     }
72 }
73 
74 void Output()
75 {
76     int ans_num = 0;
77     for (int i = 1; i <= people; i++)
78     {
79         if (!vis[i] || wait[i])
80             ans[++ans_num] = i;
81     }
82     printf("%d
", ans_num);
83     if (!ans_num)
84         return;
85     for (int i = 1; ans_num && i <= ans_num; i++)
86         printf("%d ", ans[i]);
87     puts("");
88 }
89  
90 int main()
91 {
92     Input();
93     Make_wait();
94     Work();
95     Output();
96     return 0;
97 }