Codeforces #398 Div2 D. Cartons of milk

今回問題文が長くてつらかった。
http://codeforces.com/contest/767/problem/D

問題

今冷蔵庫にN個の牛乳があり、それぞれ賞味期限はF[i]である。
ここで、店にはM個の牛乳があり、賞味期限はS[j]である。

牛乳を1日K個ずつ消費するとする。
賞味期限切れの牛乳が1個も存在しないような範囲で、できるだけ多く牛乳をまとめ買いしたい。
最大何個の牛乳を変えるか。

解法

飲む方は賞味期限が近いものから飲むのが最適だし、買う際は賞味期限が遠いものから買うのが最適である。
よって買う牛乳の数を二分探索すれば、買う牛乳が決まり、飲む順番も自明に決まるので、あとは賞味期限切れが生じるかどうかシミュレーションすればよい。

int N,M,K;
int F[1010101];
pair<int,int> S[1010101];

int ok(int num) {
	if(num>M) return 0;
	
	int day=0;
	int x=0,y=M-num,i;
	while(x<N || y<M) {
		FOR(i,K) {
			if(x==N && y==M) return 1;
			if(x!=N && (y==M || F[x]<S[y].first)) {
				if(F[x]<day) return 0;
				x++;
			}
			else {
				if(S[y].first<day) return 0;
				y++;
			}
		}
		day++;
	}
	return (x==N && y==M);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,N) cin>>F[i];
	sort(F,F+N);
	FOR(i,M) {
		cin>>S[i].first;
		S[i].second=i;
	}
	sort(S,S+M);
	
	int ret=0;
	if(!ok(0)) return _P("-1\n");
	for(i=19;i>=0;i--) if(ok(ret+(1<<i))) ret+=1<<i;
	
	vector<int> R;
	FOR(i,ret) R.push_back(S[M-1-i].second+1);
	sort(ALL(R));
	_P("%d\n",R.size());
	FORR(r,R) _P("%d ",r);
	_P("\n");
	
}

まとめ

これはすんなり。