很多大佬是的题解写的都很清楚
我想稍微解释一下为什么要cow[i] = {w + s, s};
因为排序的时候是根据牛的重量和强壮值大小进行排序的
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 50010;
PII cow[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++ i) {
int w, s;
scanf("%d%d", &w, &s);
cow[i] = {w + s, w};
}
sort(cow, cow + n);
int res = -1e9;
for (int i = 0, sum = 0; i < n; ++ i) {
int w = cow[i].second, s = cow[i].first - w;
res = max(res, sum - s);
sum += w;
}
printf("%d\n", res);
return 0;
}
大佬,我想问一下,已经排好序后,最后的最小值不就是最后一个吗,为什么还要用res比较,直接用n-1的重量-sn不行吗。。
最大风险的牛不一定是最后一个牛, 你自己随机生成数据, 可以找到很多反例.
其中一个反例:
5 10
19 2
3 24
最大风险的是第二个.