A22 贪心 • EH's Blog

题目情境#

https://www.luogu.com.cn/problem/P1842 ↗

题目描述

Farmer John 养了 $N$ 头牛，她们已经按 $1\sim N$ 依次编上了号。FJ 所不知道的是，他的所有牛都梦想着从农场逃走，去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的秋千上站稳（她们还尝试过把自己装在大炮里发射出去，但可想而知，结果是悲惨的）。最终，她们决定练习一种最简单的杂技：把所有牛都摞在一起，比如说，第一头牛站在第二头的身上，同时第二头牛又站在第三头牛的身上……最底下的是第 $N$ 头牛。

每头牛都有自己的体重以及力量，编号为 $i$ 的奶牛的体重为 $W_i$ ，力量为 $S_i$ 。

当某头牛身上站着另一些牛时它就会在一定程度上被压扁，我们不妨把它被压扁的程度叫做它的压扁指数。对于任意的牛，她的压扁指数等于摞在她上面的所有奶牛的总重（当然不包括她自己）减去她的力量。奶牛们按照一定的顺序摞在一起后，她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。

你的任务就是帮助奶牛们找出一个摞在一起的顺序，使得总压扁指数最小。

输入格式

每头牛都有自己的体重以及力量，编号为 $i$ 的奶牛的体重为 $W_i$ ，力量为 $S_i$ 。

你的任务就是帮助奶牛们找出一个摞在一起的顺序，使得总压扁指数最小。

第一行一个整数 $N$ 。

接下来 $N$ 行，每行两个整数 $W_i$ 和 $S_i$ 。

输出格式

一行一个整数表示最小总压扁指数。

输入输出样例

输入 #1

plaintext

输出 #1

plaintext

说明/提示

对于 $100\%$ 的数据， $1 \le N \le 5\times 10^4$ ， $1 \le W_i \le 10^4$ ， $1 \le S_i \le 10^9$ 。

算法解析#

本题的关键在于找到一个排序，使得每头牛受到的压扁指数尽可能小。一个常见贪心方法是按照 $W_i+S_i$ 升序排序：

若牛 $i$ 在牛 $j$ 上方，则牛 $j$ 需要承受的总重量中包含 $W_i$ ；
排序后，前面的牛更适合放在上层，因为它们相对较轻且力量较小；
这样可以使得每一次累积的总重量与当前牛的力量差值更小。

具体做法：先按照 $W_i+S_i$ 升序排序所有奶牛，然后依次将它们放到塔上，记录当前已放入的上层牛总重 $t$ ，并更新压扁指数为 $t-S_i$ 的最大值，最终得到最小的总压扁指数。

这种排序+扫描的过程时间复杂度为 $O(N \log N)$ 。

Python代码实现#

n = int(input())
a = []
for i in range(n):
    w, s = map(int, input().split())
    a.append((w, s, w + s))
a.sort(key=lambda x: x[2])
res = int(-2e9)
t = 0
for i in range(n):
    res = max(res, t - a[i][1])
    t += a[i][0]
print(res)

python

C++代码实现#

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

const int N=50005;
struct node{
  int w,s;
  bool operator<(node &t){
    return w+s<t.w+t.s;
  }
}a[N];

int main(){
  int n; cin>>n;
  for(int i=1; i<=n; i++)
    cin>>a[i].w>>a[i].s;
  sort(a+1,a+n+1);

  int res=-2e9, t=0;
  for(int i=1; i<=n; i++){
    res=max(res,t-a[i].s);
    t+=a[i].w;
  }
  cout<<res<<endl;
}