Cow Acrobats POJ3045

投稿日：2022/09/12 更新日:2022/09/12

問題

$N$ 匹の牛がいます。牛 $i$ の重さは $w_i$ 、強さは $s_i$ です。今、牛を縦に積み重ねます。この時、牛のリスクは上に乗っている牛の重さ(自分自身は含めない)の総和から自身の強さを引いた値です。リスクが最小になるように牛を積み重ねた時の最大のリスクを出力してください。

解法

牛 $i$ と $j$ ただし $(i < j)$ を考えます $i+1$ から $j-1$ までの重さを $W$ とします。この時、 $i,j$ を入れ替え無ければリスクは $W + w_j - s_i$ 、入れ替えれば $W + w_i - s_j$ となります。 $i,j$ を入れ替える方が良い場合というのは以下の式の場合です。

\begin{aligned} W + w_j - s_i &> W + w_i - s_j \\ w_j - s_i &> w_i - s_j \end{aligned}

つまり、間に何匹牛がいるかは関係なく、 $w_j - s_i > w_i - s_j$ であれば入れ替えた方が良いことが分かります。

実装

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Cow{
    int w, s;
    bool operator< (Cow b){
        return b.w - s < w - b.s;
    }
};

int main(){
    int n;
    cin >> n;
    vector<Cow> ws(n);
    for(int i = 0;i < n; ++i){
        cin >> ws[i].w >> ws[i].s;
    }

    sort(ws.begin(), ws.end());

    int sum = 0;
    int ans = -1e9;
    for(int i = n-1;i >= 0; --i){
        ans = max(ans, sum - ws[i].s);
        sum += ws[i].w;
    }

    cout << ans << endl;

    return 0;
}