其他牛的危险值显然不变，所以分析交换前后这两头牛中最大的危险值即可。

分析确实很清楚，但是还是再加一句话：第 i 头牛在第 i + 1 头牛的上面

确实，我也在这里卡了

这种结论是怎么想出来的，很好奇

这道题目对每一头牛来说最大危险系数不应该是它在最底下的时候吗？

是的，但是根据我的理解要保证最大危险系数最小，这个牛放在哪里还需要考虑这个牛的质量，而仅考虑吧一头牛的风险系数没有考虑这个牛的质量

为什么 为什么 比较$wi−si+1wi−si+1, wi+1−siwi+1−si$ 即可 ？

因为题目的要求是最大值中风险值最小
即交换后的max(wi+1−si,−si+1) 需要小于等于 交换前的max(−si,wi−si+1)
由此可推得如上不等式

请问怎么推？

我不理解？

题目要求的是最大风险值的最小可能值，在只有i和i+1两头牛的情况下：
最大风险值的范围是(-Si, Wi - Si+1, Wi+1-Si, -Si+1)
由于Si, Wi, Wi+1, Si+1的值均大于0
可得Wi - Si+1 > -Si+1, Wi+1-Si > -Si，即最大风险范围是 (Wi - Si+1, Wi+1-Si)
综上，比较 Wi - Si+1, Wi+1-Si两个值的大小就可以了

根据题意，只需要比较交换前后的风险最大值，这俩已经分别大于对方的另一个了，所以最后只需要比较这两个就可以了

按照 d = Si + Wi 的升序对奶牛进行排序并不能保证每头奶牛的风险值尽可能小。下面是一个简单的例子来说明这一点。

假设有两头奶牛 A 和 B，它们的重量分别为 Wa = 2 和 Wb = 3，强壮程度分别为 Sa = 4 和 Sb = 1。那么，我们有 Wa + Sa = 6 和 Wb + Sb = 4。

如果我们按照 d = Si + Wi 的升序对奶牛进行排序，那么奶牛 B 会排在奶牛 A 的下面。在这种情况下，奶牛 A 的风险值为 Wb - Sa = -1，奶牛 B 的风险值为 0。因此，最大风险值为 -1。

但是，如果我们将奶牛 A 放在奶牛 B 的下面，那么奶牛 A 的风险值为 0，奶牛 B 的风险值为 Wa - Sb = 1。因此，最大风险值为 1。

由于 -1 < 1，所以按照 d = Si + Wi 的升序对奶牛进行排序并不是最优的。

这个例子说明，按照 d = Si + Wi 的升序对奶牛进行排序并不能保证每头奶牛的风险值尽可能小。

您可以参考这个例子来理解这个问题。
newbing给的wi+si升序不成立的证明，我怎么感觉是对的

你理解反了，升序排列是让“奶牛 B 会排在奶牛 A 的下面”。

import java.util.*;


public class Main{

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        List<PIIs> list = new ArrayList<PIIs>();
        int n = scan.nextInt();
        for(int i = 0;i < n;i++)
        {
            int w = scan.nextInt();
            int s = scan.nextInt();
            list.add(new PIIs(w + s,w));
        }
        Collections.sort(list);
        int res = Integer.MIN_VALUE;
        int sum = 0;//记录危险值
        for(PIIs item : list)
        {
            int w = item.getSecond();
            int s = item.getFirst() - w;
            res = Math.max(res, sum - s);
            sum += w;
        }
        System.out.println(res);

    }

}



class PIIs implements Comparable<PIIs>{
    private int first;
    private int second;

    public int getFirst()
    {
        return this.first;
    }
    public int getSecond()
    {
        return this.second;
    }
    public PIIs(int first,int second)
    {
        this.first = first;
        this.second = second;
    }
    @Override
    public int compareTo(PIIs o) {
        // TODO 自动生成的方法存根
        return Integer.compare(first, o.first);
    }
}

这个把所有代码框起来是怎么操作的大佬

跟打卡时一样的

good~

牛牛牛

//这题说到底，是不是就要是要摆列的牛尽量w大的放下面，w小的放上面啊
//类比到人，你说一个100斤的人和一个200斤的人，你觉得谁在上谁在下更稳一点？

算法题不能用现实来类比，你完全可以看到一个体重为99999999而力气为1的牛，也可以看到一个体重为1而力气为99999999的牛，那么排序就是个抽象的问题了:]

但是你说的特殊栗子啊，他这题是要贪心求最优解啊

牛牛牛

orz

太牛了啊大佬，给大佬跪一个orz

#include [HTML_REMOVED]
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int N = 1e5 + 5;

struct pos {
int w, s, val;
} a[N];

bool cmp(pos &x, pos &y) {
return x.val > y.val;
}

void solve() {
int n;
cin >> n;
long long ans = -1e18;
long long sum = 0;
for (int i = 1; i <= n; i) {
cin >> a[i].w >> a[i].s;
a[i].val = a[i].w + a[i].s;
sum += a[i].w;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i) {
ans = max(ans, sum - a[i].val);
sum -= a[i].w;
}
cout << ans;
}

int main() {
IOS;
int ;
_ = 1;
while (–)
solve();
return 0;
}

为什么危险值最大的不是最后一头牛？而是每一个都取max呀。友友们

还要考虑牛的强壮程度吧，风险值=取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值
如果最后一头牛强壮程度无限大，那么最后一头牛的风险值不一定是最大的

Orz

这样也可以的QAQ

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

const int N = 500010;
int n;
int w[N], s[N];
vector<pair<int, int>> a;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> w[i] >> s[i], a.push_back({w[i] + s[i], i});
    sort(a.begin(), a.end());
    int res = -s[a[0].second], aw = 0;
    for(int i = 0; i < n; i++)
        if(i){ 
        aw += w[a[i - 1].second];
        res = max(res, aw - s[a[i].second]);
        }

    cout << res;
    return 0;
}

这个把所有代码框起来是怎么操作的

评论区支持markdown，你用```把将代码包起来就可以

和打卡那个一样的

Orz

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4+10;
using LL = long long;
using PLL = pair<LL,LL>;
#define x first
#define y second
PLL q[N];

int n;

int main()
{
    scanf("%d",&n);
    LL sum=0;
    for(int i=0;i<n;++i){
        scanf("%ld%ld",&q[i].x,&q[i].y);
        sum+=q[i].x;
    }

    sort(q,q+n,[](const auto& a,const auto& b){
        return a.x+a.y>b.x+b.y;
    });

    LL res=-1e16;
    for(int i=0;i<n;++i){
        sum-=q[i].x;
        res=max(res,sum-q[i].y);
    }
    cout<<res<<endl;
    return 0;
}

这个把所有代码框起来是怎么操作的

Orz 大佬见多了，我就有深深的自卑感