Acwing 贪心算法遗留-4.推公式

Acwing 125.耍杂技的牛

实现思路：wi表示牛的体重，si表示牛的强壮度
先给结论：按照w + s从小到大的顺序，从上往下排，最大的危险系数一定是最小的。

简单理解：把重量轻的牛放下面是很亏的，同样把不强壮的牛放下面也是亏的，所以就尽可能把又重又强壮的牛放下面

就不证明了。

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int,int> PII;//存储牛的体重+强健度，体重
const int N = 50010;

PII cow[N];
int n;

int main(){
    cin >> n;
    for(int i = 0 ; i < n ; i ++){
        int w,s;
        cin >> w >> s;
        cow[i] = {w + s,w};
    }
    sort(cow ,cow + n);//自动先按体重+强健度排序
    int sum = 0,res = -2e9;
    
    for(int i = 0 ; i < n ; i ++){
        int w = cow[i].second,s = cow[i].first - w;//s为强健度
        res = max(res,sum - s);
        sum += w;
    }
    
    cout << res << endl;
}

总结：贪心算法（Greedy Algorithm）是一类在每一步选择中都采取当前最优策略，以期最终获得全局最优解的算法。贪心算法非常适用于解决局部最优能够导出全局最优的场景。在实际应用中，贪心算法通常比动态规划和回溯算法更为简单高效，但它并不总是能保证找到最优解。因此，贪心算法的应用需要证明其贪心策略是正确的，确保每一步的局部最优解能够累积成为全局最优解。

完结撒花~多复习