2016-10-31

Codeforces 732D Exams【二分+贪心】

题目链接：

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

题意：

给定每天可以考试的科目以及每个科目必须的准备天数，准备过程可以不连续，问你最少多少天能考完？不能考完输出$-1$

分析：

首先明确越靠后考试越能保证足够的复习时间
二分天数，判断的时候对于每个科目都贪心选择在最后一个能考的天考，最后看能否在给定时间内复习完即可。

代码:

/*************************************************************************
    > File Name: 732.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/24 18:58:16
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int a[maxn], d[maxn];
bool vis[maxn];
int n, m;
bool judge(int k)
{
	int tot = 0, cnt = 0;
	memset(vis, false, sizeof(vis));
	for(int i = k; i >= 1; --i){
		int t = d[i];
		if(!t && !cnt) continue;
		if(vis[t] || !t) tot--;
		else{
			vis[t] = true;
			cnt++;
			tot += a[t];
		}
		if(tot < 0) tot = 0;
	}
	return tot == 0 && cnt == m;
}
int main (void)
{
	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 = 0, r = n;
	while(l < r - 1){
		int mid = l + r >> 1;
		if(judge(mid)) r = mid;
		else l = mid;
	}
	if(r == n && !judge(n)) puts("-1");
	else printf("%d\n", r);
	return 0;
}