Codeforces #429 Div1 A. Leha and Function

Dが落ちたけどなんとかレート増。
http://codeforces.com/contest/840/problem/A

問題

以下の関数を考える。
f(n,k) := 1～nの整数のうちk個ランダムに選んだ時の最小値の期待値

ここでN要素の2つの数列A[i],B[i]が与えられる。
Aを並べ替え、sum(f(A[i],B[i]))を最大となるようにせよ。

解法

サンプルから想像がつくが、B[i]の大きなところにA[i]の小さい値が来るように並べ替えるだけ。

int M;
int A[202020],B[202020],C[202020];
pair<int,int> P[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,M) cin>>A[i];
	FOR(i,M) cin>>B[i], P[i]={B[i],i};
	sort(A,A+M);
	sort(P,P+M);
	FOR(i,M) C[P[M-1-i].second]=A[i];
	FOR(i,M) _P("%d%c",C[i],(i==M-1)?'\n':' ');
	
}

まとめ

真面目に問題読むと損する感じの問題。