「贪心」耍杂技的牛

耍杂技的牛

题目大意

给你(n)头牛，每头牛有一个重量 (w_i) 和强壮程度 (s_i)，现在要把牛叠起来，每头牛有一个风险值，这个风险值当前这头牛头上的所有牛重量加起来减去当前这头牛的强壮程度，要使这个值最大值最小

题目题解

本来以为是个二分题，但是发现二分并没有办法处理，这仅在一个堆上面处理，那就考虑下贪心，发现两个值，可以用类似国王游戏的想法来搞定，于是随便列了个等式 (w_i + s_i) ,用这个等式升序排列，怎么列的... 因为就乘和加比较好处理。

那如何证明呢？先将随意两个位置的牛交换位置

ID	交换前	交换后
(i)	(Sigma_{j = 1}^{i - 1}w_j - s_i)	(Sigma_{j = 1}^{i - 1}w_j + w_{i + 1} - s_i)
(i + 1)	(Sigma_{j = 1}^{i}w_j - s_{i + 1})	(Sigma_{j = 1}^{i - 1} - s_{i + 1})

然后化简可得

ID	交换前	交换后
(i)	(-s_i)	(w_{i + 1} - s_i)
(i + 1)	(w_i-s_{i + 1})	(-s_{i + 1})

因为s,w都是正整数，所以 (-s_i < w_{i + 1} - s_i) 、(w_i-s_{i + 1} > -s_{i + 1})

那么现在我们就需要比较 (与w_i - s_{i + 1} 与 w_{i + 1} - s_i)

若 (w_i - s_{i + 1} ≤ w_{i + 1} - s_i) ，即(w_i + s_i ≤ w_{i + 1} + s_{i + 1}) 时交换前最优

若 (＞w_i - s_{i + 1} ＞ w_{i + 1} - s_i)，即(＞w_i + s_i ＞ w_{i + 1} + s_{i + 1}) 时交换后最优

那么根据这两个我们随便按升序降序排序都可以解决这道题了

代码如下

//#define fre yes

#include <cstdio>
#include <iostream>
#include <algorithm>

const int N = 50005;
struct Node {
    int w, s, sum;
} q[N];

bool cmp(Node x, Node y) {
    return x.sum < y.sum;
}

int main() {
    static int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &q[i].w, &q[i].s);
        q[i].sum = q[i].w + q[i].s;
    } std::sort(q + 1, q + 1 + n, cmp);
    long long ans = -1e18, sum;
    for (int i = 1; i <= n; i++) {
        sum -= q[i].s;
        ans = std::max(ans, sum);
        sum += q[i].sum;
    } printf("%lld
", ans);
    return 0;
}