推公式

原题链接：125. 耍杂技的牛 - AcWing题库

题意：牛危险系数定义为：上面的牛的重量和减去自身的强壮度，牛与牛叠罗汉，问怎么叠最大的风险值最小

思路

列公式推

推公式 2024-03-22 00.20.47.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Excalidraw Data

Text Elements

w重量，s强壮

有 每头牛风险 w1 + w2 + w3 …… w(i-1) - s(i) 要找w与s关系，分析下一头牛才有这头牛的w 下一头牛 w1 + w2 + w3 …… w(i) - s(i+1)

去掉重复部分，两头牛的风险为 -s(i) 和 w(i) - s(i+1)

如果上面的是最大值 w(i)+s(i)<s(i+1) 如果下面是最大值 w(i)+s(i)>s(i+1)

如果交换？-s(i+1) 和 w(i+1) - s(i) w(i+1)+s(i+1)<s(i) 假设i+1的w+s大于i的 w(i+1)+s(i+1)>s(i) 那么谁的最大值小？

不妨都加上s(i)+s(i+1) 即：s(i+1) w(i)+s(i) s(i) w(i+1)+s(i+1) 可知，下面的最大值大于上面的，即交换之后，w+s大的牛在 下面会导致最大值变大

同时分析这两头牛时其他牛不受影响

Link to original

即按w+s从小到大排序，从上到下叠

实现

#include <iostream>
#include <algorithm>
 
 
using namespace std;
 
const int N = 5e4 + 10;
 
typedef long long LL;
typedef pair<LL, LL> PII;
 
PII cow[N];
 
int main()
{
    int n;
    cin >> n;
    
    for(int i =  0 ; i < n; i ++)
    {
        int w, s;
        cin >> w >> s;
        cow[i].first = w+s;
        cow[i].second = w;
    }
    
    sort(cow, cow + n);
    
    LL ans = -2e9;
    LL W = 0;
    for(int i = 0; i < n; i ++)
    {
        int w = cow[i].second;
        //int s = cow[i].first - w;
        W += w;
        
        ans = max(ans, W - cow[i].first);
    }
    
    cout << ans << endl;
    
    return 0;
}