D Exams（二分）

题目链接：

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

题意：给出n,m然后给出n天的计划（第i天考试考试科目）再给出m个数表示第i个的预习时间，问多少天能把所有的科目考完？？

思路：用二分法找出天数k然后从第k天往第1天推，如果满足当前所需天数小于k则把当天的天数减去该科目的预习时间+1，进行下一次判断。

AC代码：

 1  #include <iostream>
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 int a[100005],d[100005],dd[100005];
 5 int n,m,sum,l,r,ans,mid;
 6 int cheak(int k)
 7 {
 8     int need=sum+m;
 9     for(int i=1;i<=m;i++)
10         dd[i]=0;
11     for(int i=k;i>=1;i--)
12     {
13         if(a[i]==0)
14             continue;
15         if(!dd[a[i]])
16         {
17             if(need>i)
18                 return 0;
19             need-=d[a[i]]+1;
20             dd[a[i]]=1;
21         }
22     }
23     for(int i=1;i<=m;i++)
24         if(!dd[i]) return 0;
25     return 1;
26 }
27 int main()
28 {
29     while(~scanf("%d%d",&n,&m))
30     {
31         sum=0;
32         for(int i=1;i<=n;i++)
33             scanf("%d",&a[i]);
34         for(int i=1;i<=m;i++)
35             scanf("%d",&d[i]),sum+=d[i];
36         if(sum+m>n)
37         {printf("-1
");continue;}
38         l=1;r=n;ans=-1;
39         while(l<=r)
40         {
41             mid=(l+r)/2;
42             if(cheak(mid))
43             {
44                 ans=mid;
45                 r=mid-1;
46             }
47             else
48                 l=mid+1;
49         }
50         printf("%d
",ans);
51     }
52     return 0;
53 }

View Code