yukicoder : No.2770 Coupon Optimization

思いつくまでちょっとかかった。
https://yukicoder.me/problems/no/2770

問題

N個の商品があり、それぞれ価格が与えられる。
加えて、M枚のクーポンがあり、それぞれを使うと1つの商品を指定のパーセント(整数)だけ割引できる。
クーポンは商品一つにつき1枚しか使えない。

商品を1～N個買うとき、それぞれ最適にクーポンを使うことで得られる、必要な価格の最小値を求めよ。

解法

K個商品を買うとき、商品のうち安い方からK個を買えばよい。
その際、クーポンのうち割引率の大きな物から順に、価格の高いものに適用したい。
愚直に行うと、O(K)かけて計算しないといけない。

ここで、クーポンの割引率が整数であることを利用する。

• 100%引きで買う商品がxx個
• 99%引きで買う商品がxx個
• 98%引きで買う商品がxx個

…
と考えて行くと、商品を安い順に並べた場合の価格の累積和を使えば、K1つに対し割引率101通りの価格を累積和で足せばよくなる。

int N,M;
int A[202020];
int B[101];
ll SA[402020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i];
		A[i]/=100;
	}
	B[100]=1000000;
	FOR(i,M) {
		cin>>x;
		B[100-x]++;
	}
	sort(A,A+N);
	reverse(A,A+N);
	FOR(i,N) {
		SA[i+1]=SA[i]+A[i];
	}
	for(i=1;i<=N;i++) {
		int cur=N-i;
		ll ret=0;
		FOR(j,101) {
			x=min(N-cur,B[j]);
			ret+=(SA[cur+x]-SA[cur])*j;
			cur+=x;
		}
		cout<<ret<<endl;
	}
	
	
}

まとめ

思いつけばすんなり。