CodeForces - 732D Exams
Whiteying
2018-11-12 23:20:18
# B类
题外话：比赛的时候尝试过，但不是用的二分，用的暴力，但是没有TLE，是WA掉了，神奇。。。。
# 题目链接：
https://vjudge.net/problem/CodeForces-732D
# 题意:
你每天可以做三件事，考试、复习、或者休息。
每门课都有一个需要复习的天数，比如第i门课需要复习ai天，只有当你总共复习了ai天的第i门课，你才能在考试中通过这第i门课。当然，你也不用非得连续几天都复习一门课，可以穿插着复习，只要最后的天数满足就可以了。
为了尽早回家，你想计算出考完这m门课最少需要多少天？当然每门课都要考通过。要是怎么也不能全部通过，那就输出-1。
# 解题思路:
利用二分的思想,找出最优的天数.
假定出一个天数,然后从后往前遍历.
如果第一次遇到某种考试,那么就让你所有要复习的天数减去这门课要考的天数,同时把这种课标记掉.
如果你遍历到某一天是0或者是这一门已经被标记掉了,那么就让所有剩余的天数减一,因为你这一天拿来复习了.
当然,如果你剩余的天数小于你总的需要复习的天数,那么就返回错误.
遍历完成,看一下剩余的天数是否为0,如果为0就返回正确,否则返回错误.
# AC代码：
```cpp
#include<iostream>
using namespace std;
int n,m;
int a[100005],b[100005];
bool judge(int time)
{
int sum=0;
int vis[100005]={0};
for(int i=time;i>=1;i--)
{
if( a[i] && vis[a[i]]!=0 )
{
sum+=b[a[i]];
vis[a[i]]=1;
}
else if(sum!=0)
sum--;
}
for(int i=1;i<=m;i++)
if(vis[i]==0)
return false;
if(sum!=0)
return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
int left=1,right=n;
while(left<right)
{
int middle=(left+right)/2;
if(judge(middle)==false)
left=middle+1;
else
right=middle;
}
if(judge(left)==true)
printf("%d\n",left);
else if(judge(right)==true)
printf("%d\n",right);
else
printf("-1\n");
return 0;
}
```