Codeforces #591 Div1 A. Save the Nature

これUnratedだった奴だっけ。
https://codeforces.com/contest/1240/problem/A

問題

N種類のチケットを売ることを考える。各チケットは1枚ずつで、その価格はP[i]である。
チケットの販売順は任意とする。
なお、A枚目ごとにその時の販売チケットの金額のX%を寄付し、B枚目ごとにその時の販売チケットの金額のY%を寄付する。
両者は重複することもあり、LCM(A,B)毎ごとに(X+Y)%寄付する。

寄付金額がK以上になるには、チケットを最低何枚売らなければならないか。

解法

販売枚数を二分探索しよう。
枚数が決まれば(X+Y)%、X%、Y%の寄付を行うチケットの枚数が確定するので、高いチケットを高い寄付割合のものに割り当てればよい。

int Q;
int N;
ll P[202020];
ll X,A,Y,B,AB;
ll K;

int ok(int v) {
	ll NAB=v/AB;
	ll NA=v/A-NAB;
	ll NB=v/B-NAB;
	if(v<=0) return 0;
	ll ret=0;
	int i;
	
	FOR(i,v) {
		if(ret>=K) return 1;
		if(NAB) {
			NAB--;
			ret+=P[i]*(X+Y);
		}
		else if(NA) {
			NA--;
			ret+=P[i]*X;
		}
		else if(NB) {
			NB--;
			ret+=P[i]*Y;
		}
		else break;
	}
	return ret>=K;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>N;
		FOR(i,N) {
			cin>>P[i];
			P[i]/=100;
		}
		sort(P,P+N);
		reverse(P,P+N);
		cin>>X>>A;
		cin>>Y>>B;
		if(X<Y) swap(X,Y), swap(A,B);
		cin>>K;
		
		AB=A*B/__gcd(A,B);
		
		int ret=N;
		if(ok(N)==0) {
			cout<<-1<<endl;
		}
		else {
			for(i=20;i>=0;i--) {
				if(ok(ret-(1<<i))) ret-=1<<i;
			}
			cout<<ret<<endl;
		}
		
		
	}
}

まとめ

もっと簡単に書けないかな。