Codeforces #398 Div2 E. Change-free

気づけば簡単なのね…。
http://codeforces.com/contest/767/problem/E

問題

100ルーブル札が無限枚と、1ルーブルコインがM個ある。

ここで、N回店で買い物をする。
i回目に買うものの値段はC[i]である。
その際、おつりが生じた場合、お釣りのお札の数とコインの数の和に、W[i]を掛けた分だけ店主が不愉快になる。

お釣りで得たコインは、以後も利用可能であるとする。
最終的に店主の総不愉快度が最小になる支払い方を求めよ。

解法

お釣りにお札が入る払い方をする意味はないので、払い方は100ルーブル単位はお札で支払、不足分をコインでピッタリ払うか、コインが足りないときはお札を1枚余分に払うかである。

ここで、お札を余分に払うとはどういうことかを考える。
ピッタリ払う場合、コインはC[i]%100個消費する。
逆にお釣りをもらう場合、コインは100-C[i]%100個増加する。

これを言い換えると、後者はお札1枚をコイン100個にしたうえで、C[i]%100個消費する、と言い換えられる。
こう考えると、どのみちコインはC[i]%100個消費すると考えられ、各回において、1回だけ不愉快度をW[i]*(100-C[i]%100)増加させてコインを100枚取得できると考えられる。

ここまで来るとあとは簡単で、Priority_Queueでまだお釣りをもらってない日の不愉快度W[i]*(100-C[i]%100)を小さい順に管理しておき、コインが足りなくなりそうなときは不愉快度の小さい(まだお釣りをもらってない)日を選んで100毎コインをもらえばよい。

int N,M;
int C[101010],W[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>C[i];
	FOR(i,N) cin>>W[i];
	
	priority_queue<pair<int,int>> PQ;
	ll cost=0;
	FOR(i,N) {
		if(C[i]%100==0) continue;
		PQ.push({-W[i]*(100-C[i]%100),i});
		M-=C[i]%100;
		while(M < 0) {
			cost += -PQ.top().first;
			C[PQ.top().second]+=100-C[PQ.top().second]%100;
			M+=100;
			PQ.pop();
		}
	}
	cout<<cost<<endl;
	FOR(i,N) cout<<C[i]/100<<" "<<C[i]%100<<endl;
	
}

まとめ

本番はEわからないしCが落ちるの確定してしまったので、30分以上残して抜けてしまったのよね。