耍杂技的牛

发表于 | 更新于 | 分类于

农民约翰的N头奶牛（编号为1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这N头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度Si。

一头牛只撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入格式

第一行输入整数N，表示奶牛数量。

接下来N行，每行输入两个整数，表示牛的重量和强壮程度，第i行表示第i头牛的重量Wi以及它的强壮程度Si。

输出格式

输出一个整数，表示最大风险值的最小可能值。

数据范围

1≤N≤50000,
1≤Wi≤10,000,
1≤Si≤1,000,000,000

输入样例：

1
2
3
4
3
10 3
2 5
3 3

输出样例：

1
2

题意:

给你N头牛，每头牛有两个属性w(重量值)，s(强壮值)，危险值 = 前面所有牛的总重量 - 它身体强壮程度的值, 安排一个顺序使得
所有牛中的最大危险值最小

(贪心)

思路: 与国王游戏的贪心策略相似， 我们先分析每头牛的危险值 = 他前面牛的w(重量值)和 - 自身的s(强壮值)，要使每头牛的危险值最小，这显然是与w 和 s同时相关，所以先 yy 出一种做法按 每头牛的w + s进行升序排序(题见多了可能就会有这种题感)。接下来进行数学分析证明:

牛 交换前 交换后
$i$ $$\sum_{j=1}^{i-1} w_j - s_i$$ $$\sum_{j=1}^{i-1} w_j + w_{i+1}- s_i$$
$i + 1$ $$\sum_{j=1}^{i} w_j - s_{i+1}$$ $$\sum_{j=1}^{i-1} w_j - s_{i+1}$$

其他牛的危险值显然不变，所以分析交换前后这两头牛中最大的危险值即可。
将上述式子进行化简，每个式子减去 $\sum_{j=1}^{i-1} w_j$得到如下式子

牛 交换前 交换后
$i$ $$-s_i$$ $$w_{i+1}- s_i$$
$i + 1$ $$w_i- s_{i+1}$$ $$- s_{i+1}$$

由于s, w都是正数，$w_i- s_{i+1} > - s_{i+1}$ , $w_{i+1}- s_i > -s_i$

比较$ 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}$时, 交换前更优

所以得到做法: 按每头牛的 w + s 进行排序, 当存在逆序时就进行交换(即升序排序)，
然后根据题意算出每头牛的危险值记录其中的最大值即可
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 5e4 + 5;
PII a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d %d", &x, &y);
        a[i].first = x + y;
        a[i].second = y;
    }
    sort(a, a + n);
    ll res = -1e18, sum = 0;
    for(int i = 0; i < n; i ++ )
    {
        sum -= a[i].second;
        res = max(res, sum);
        sum += a[i].first;
    }
    cout << res << endl;
    return 0;
}

0%