codeforces 732D(二分)

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

题意:有m门需要过的课程,n天的时间可以选择复习、考试(如果的d[i]为0则只能复习),一门课至少要复习a[i]天才能通过,问最早什么时候可以把所有课程都通过,如果不能输出-1。

思路:二分判断,比赛时不会check...具体见注释。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,m,d[N],a[N];
bool flag[N];
bool check(int x)
{
memset(flag,0,sizeof(flag));
int cur = x - 1;//cur为当前剩余复习天数
for(int i = x; i >= 1; i--)
{
cur = min(cur, i - 1);//最多也只能是i - 1天的复习时间
if(d[i] && !flag[d[i]] && a[d[i]] <= cur)
{
flag[d[i]] = 1;
cur -= a[d[i]] + 1;//+1为下次考试所占的一天
}
}
for(int i = 1; i <= m; i++)
{
if(!flag[i])
return 0;
}
return 1;
}
int main()
{
int ans = -1;
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++)
scanf("%d",d+i);
for(int i = 1; i <= m; i++)
scanf("%d",a+i);
int l = 1, r = n, mid;
while(l <= r)
{
mid = (l + r) >> 1;
if(check(mid))
r = mid - 1, ans = mid;
else
l = mid + 1;
}
printf("%d\n",ans);
}
上一篇:Win10 安装MySQL 5.7.32(解压版)


下一篇:解决win10安装MySQL数据库出现服务无法启动的问题