Codeforces Round #377 (Div. 2) D. Exams 二分

D. Exams

链接：

http://codeforces.com/contest/732/problem/D

题解：

二分答案，只需要判断能不能完成就行了，

判断的时候从后往前遍历，遇到的第一个考试时间就加入队列，

如果已经加入队列或者没有考试，就优先复习队列前面的课程，

最后判断一下是不是所有的需要复习的天数都为0就行了

代码：

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int maxn = 1e5 + 7;
 7 int d[maxn], a[maxn];
 8 int _d[maxn], _a[maxn], vis[maxn];
 9 int n, m;
10 
11 bool C(int x) {
12     memset(vis, 0, sizeof(vis));
13     for (int i = 1; i <= n; i++) _d[i] = d[i];
14     for (int i = 1; i <= m; i++) _a[i] = a[i];    
15     for (int i = x; i >= 1; i--) {
16         if (_d[i] && !vis[_d[i]]) vis[_d[i]] = 1;
17         else _d[i] = 0;
18     }
19     queue<int> mq;
20     for (int i = x; i >= 1; i--) {
21         if (_d[i]) mq.push(_d[i]);
22         else if (!mq.empty()) {
23             if (_a[mq.front()]) _a[mq.front()]--;
24             else {
25                 mq.pop();
26                 if (!mq.empty()) _a[mq.front()]--;
27             }
28         }
29     }
30     for (int i = 1; i <= m; i++)
31         if (_a[i]) return false;
32     return true;
33 }
34 
35 int main()
36 {
37     cin >> n >> m;
38     for (int i = 1; i <= n; i++) cin >> d[i];
39     for (int i = 1; i <= m; i++) cin >> a[i];
40     int l = 1, r = n + 1;
41     while (r - l > 1) {
42         int mid = (l + r) / 2;
43         if (C(mid)) r = mid;
44         else l = mid;
45     }
46     if (r <= n) cout << r << endl;
47     else cout << -1 << endl;
48     return 0;
49 }