Codeforces Round #377 (Div. 2) D. Exams
Codeforces Round #377 (Div. 2) D. Exams
题意：给你n个考试科目编号1~n以及他们所需要的复习时间ai;(复习时间不一定要连续的，可以分开，只要复习够ai天就行了) 然后再给你m天，每天有一个值di; 其中,di==0代表这一天没有考试(所以是只能拿来复习的); 若di不为0，则di的值就代表第i天可以考编号为di的科目 ;(当然这一天也可以不考而拿来复习) 。 问你最少能在第几天考完所有科目，无解则输出-1。
题解：首先，先想想最暴力的方法：从第1天到第n天这样一天天地试，每次判断前k天能否考完所有科目(至于怎么判断前k天能否够考完所有科目下面会说)。 这样子的最坏情况的复杂度是O(n^2); 那么如果不要这样一天天地判断过去的话,要进行优化；那么，由于题目要问最小天数能考完所有科目，且天数都是升序的—这时,就可以用二分了。 二分能考完所有科目的天数，每次判断该天数能否考完。 那么问题就被简化了；原来问题是最小的天数要考完所有科目，，而现在就只需关心怎么判断用前k天时间能考完所有科目 这里用贪心的方法：建立个变量sum复习需要用到的天数 ， 用第k天开始往前扫；如果di不为0(另外还要有个标记数组来标记该科目是否是第一次扫到)，则将该科目所需要的复习天数加到sum上； 如果di为0，则将sum-- (前提是sum不为0)。 扫完后，用标记数组判断是否所有科目都考了且sum是否为0 ； 若sum不为0，说明复习天数是不够用的。 最后复杂度是为O(nlogn)的。
( ps: 可能有的人会觉得从后往前扫，只有遇到的科目第一次出现时才加入到sum中，但这些都是k天内各科目的最后"期限"，虽然判断到用k天可行，但可能不是最优的(一开始自己就在这上面给坑了=_=)。 但是，因为上面已经有二分了，所以我们这后面只要关注在能不能用k天将所有科目考完，而不用理会它是不是最优的! )
下面是AC代码： 这一题的后台数据其实是有点水的，，如果发现代码有Bug的话欢迎各位提出 (o゜▽゜)o☆
1 /** 2 * @author geek1116 3 */ 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 #include <algorithm> 9 #include <queue> 10 #include <stack> 11 #include <vector> 12 #include <utility> 13 #include <map> 14 #include <set> 15 const int inf=0x3f3f3f3f; 16 const double PI=acos(-1.0); 17 const double EPS=1e-10; 18 const int MAXN=1e5; 19 using namespace std; 20 typedef long long ll; 21 typedef pair<int,int> P; 22 23 int n,m; 24 int d[MAXN+10]; 25 int a[MAXN+10]; 26 int book[MAXN+10]; //标记数组 27 28 bool judge(int x) //判断用前x天是否可行 29 { 30 memset(book,0,sizeof(book)); 31 int sum=0,cnt=0; 32 // 33 for(int i=x;i>=1;i--) 34 { 35 if(d[i]) 36 { 37 if(!book[d[i]]) sum+=a[d[i]],book[d[i]]=1,cnt++; 38 else if(sum!=0) sum--; 39 } 40 else if(sum!=0) 41 sum--; 42 } 43 // 44 if(sum||cnt!=m) return false; 45 else return true; 46 } 47 int main() 48 { 49 //freopen("input.txt","r",stdin); 50 scanf("%d%d",&n,&m); 51 for(int i=1;i<=n;i++) scanf("%d",&d[i]); 52 for(int i=1;i<=m;i++) scanf("%d",&a[i]); 53 // 54 int l=1,r=n,mid; 55 while(l<r) //二分结束天数 56 { 57 mid=(l+r)>>1; 58 if(judge(mid)) r=mid; 59 else l=mid+1; 60 } 61 // 62 if(judge(l)) printf("%d ",l); 63 else if(judge(r)) printf("%d ",r); 64 else printf("%d ",-1); 65 return 0; 66 }