Codeforces #280 Div2 C. Vanya and Exams

CF280に参加。
Div2回とはいえいつもよりだいぶ難易度が低く、割とあっさり全完。
ただDにちょっと手間取った。
http://codeforces.com/contest/492/problem/C

問題

N個の試験があり、各ランクはA[i]である。
各試験を突破する際、B[i]個のエッセイを書く毎に１つ高いランクが得られる。
ただし各試験のランクはRを超えられない。

全試験を突破するときの平均ランクをAvrにするには、最小何個エッセイを書く必要があるか。

解法

平均がAvrなので合計ランクをN*Avrにすることを考える。
当然、B[i]が低い試験から優先的にエッセイを書けば、少ないエッセイ数でランクを上げることができる。

よって、試験をB[i]昇順でソートし、合計ランクがN*Avrに到達するか、各試験のランクがRに到達するまで、順にエッセイを書く数を累積していけば良い。

int N;
ll R,AV,A[100200],B[100200];
pair<ll,ll> P[100200];
ll tot,ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>R>>AV;
	tot=AV*N;
	FOR(i,N) cin>>P[i].second>>P[i].first, tot-=P[i].second;
	sort(P,P+N);
	
	FOR(i,N) {
		ll up=max(0LL,min(tot,R-P[i].second));
		tot-=up;
		ret += up*P[i].first;
	}
	cout<<ret<<endl;
	
}

まとめ

ここらへんはまだまだ。