[Codeforces] 732D. Exams

題目連結:http://codeforces.com/problemset/problem/732/D

---

一開始想爛了，但大方向還算對，原本以為可以直接greedy算，但一直算不太出來(雖然好像還是可)。後來發現其實可以對答案二分搜，然而驗答案的地方我一直寫爛掉，導致這題寫了超久了，但最後AC code其實也沒多複雜，真搞不懂哪裡爛掉。
稍微講一下驗證答案的部分好了，就因為有個簡單的性質就是你若可以今天考，但今天不考之後再考也可以，所以驗證答案的時候都讓每科考試都在最後一次可以考時才考，這樣前面就會有一堆溫書假了。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;

int need[N], ok[N];
bitset<N> done;
bool isOK(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m; cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>ok[i];
	for(int i=1;i<=m;i++) cin>>need[i];
	int l=1, r=n+1;
	while(r-l > 1){
		int mid = (l+r)>>1;
		if(isOK(mid, m)) r=mid;
		else l=mid;
	}
	cerr<<ok[r]<<"\n";
	if(r==n+1) cout<<"-1\n";
	else cout<<r<<'\n';
	return 0;
}

bool isOK(int n, int m){
	done.reset();
	done[0]=1;
	int used = 0, ans = 0;
	for(int i=n;i>=1;i--){
		if(done[ok[i]]) used=max(used-1, 0);
		else{
			used += need[ok[i]];
			done[ok[i]]=1;
			ans++;
		}
	}
	return used==0 and ans==m;
}