codeforces 732D Exams(贪心+二分)

题目链接：http://codeforces.com/problemset/problem/732/D

题目大意：每组数据第一行包括两个数n,m,第二行是n个数，表示每i天可以通过哪一门考试（0表示这天不能通过任何一门考试），第三行是m个数，表示每门课要复习的时间。求出要通过m门考试的最小花费天数。

解题思路：贪心+二分（自己做题时想到了贪心，但还是不知道怎么去实现，同时题目的范围比较大直接贪心枚举肯定是会超时的，所以可以二分枚举优化时间复杂度）

AC代码：

#include<bits/stdc++.h>
#define mann 100005
using namespace std;
int a[mann],b[mann];
int vis[mann];
int n,m;
int judge(int x)
{
memset(vis,0,sizeof(vis));
int sum=0;
for(int i=x;i>0;i--)//贪心
{
if(a[i]!=0&&vis[a[i]]==0)//如果第i天可以考试且a[i]这门课没有被考过，用vis数组标记
{//即第i天考a[i]这门课
vis[a[i]]=1;
sum+=b[a[i]];//需要花费的时间
}
else if(sum!=0)//如果第i天不能考a[i]这门课，且sum!=0,即这一天是复习
sum--;
}
if(sum!=0)//需要的时间不够
return 0;
for(int i=1;i<=m;i++)
if(vis[i]==0)//m门课没有全部通过（考完）
return 0;
return 1;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
//int summ=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int j=1;j<=m;j++)
{
scanf("%d",&b[j]);
//summ+=b[j];
}
//
if(summ+m>=n)
//
printf("-1n");
//
else
//
{
int l=1,r=n;
while(r>l)//二分找需要的最小天数
{
int mid=(l+r)>>1;
if(judge(mid)==0)
l=mid+1;
else
r=mid;
}
if(judge(l))
printf("%dn",l);
else if(judge(r))
printf("%dn",r);
else
printf("-1n");
//
}
}
return 0;
}

最后

以上就是忧虑煎蛋为你收集整理的codeforces 732D Exams(贪心+二分)的全部内容，希望文章能够帮你解决codeforces 732D Exams(贪心+二分)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。