disastrous gemini [Kodamanと愉快な仲間たち F]

https://www.hackerrank.com/contests/kodamanwithothers/challenges/disastrous-gemini

解説

https://www.hackerrank.com/contests/kodamanwithothers/challenges/disastrous-gemini/submissions/code/1316476143

クーラーをつけないと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;
}