https://www.hackerrank.com/contests/kodamanwithothers/challenges/disastrous-gemini
解説
クーラーをつけないとAi秒、つけているとBi秒かかるというパラメタ。 クーラーを付けると、その問題についてAi-Bi秒短縮できることになる。 N問中K問について、この短縮を行うことができる。 最適なのは、短縮が大きいものだろう。 クーラーをつけていないものとして、Aiの総和を取り、短縮が大きいものからK個分、 その総和から短縮分を引いてやると答えが得られる。
最初はこの手の言い換えは難しいかもしれない。 このような言い換えをすると、A,Bという2パラメタから短縮という1パラメタに減る。 減らすことで問題が簡単になることがある。
int N, K, A[101010], B[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; rep(i, 0, N) cin >> A[i] >> B[i]; int ans = 0; rep(i, 0, N) ans += A[i]; priority_queue<int> que; rep(i, 0, N) que.push(A[i] - B[i]); rep(i, 0, K) { ans -= que.top(); que.pop(); } cout << ans << endl; }