ToB企服应用市场:ToB评测及商务社交产业平台

标题: 洛谷P1842 [USACO05NOV] 奶牛玩杂技 [打印本页]

作者: 丝 时间: 2024-8-5 10:42
标题: 洛谷P1842 [USACO05NOV] 奶牛玩杂技
[USACO05NOV] 奶牛玩杂技

题目配景

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

每头牛都有自己的体重以及力量，编号为 \(i\) 的奶牛的体重为 \(W_i\)，力量为 \(S_i\)。
当某头牛身上站着另一些牛时它就会在一定水平上被压扁，我们不妨把它被压扁的水平叫做它的压扁指数。对于任意的牛，她的压扁指数即是摞在她上面的全部奶牛的总重（当然不包括她自己）减去它的力量。奶牛们按照一定的顺序摞在一起后，她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。
你的使命就是帮助奶牛们找出一个摞在一起的顺序，使得总压扁指数最小。
输入格式

第一行一个整数 \(N\)。
接下来 \(N\) 行，每行两个整数 \(W_i\) 和 \(S_i\)。
输特别式

一行一个整数表示最小总压扁指数。
样例 #1

样例输入 #1

3
10 3
2 5
3 3

复制代码

样例输出 #1

复制代码

提示

对于 \(100\%\) 的数据，\(1 \le N \le 5\times 10^4\)，\(1 \le W_i \le 10^4\)，\(1 \le S_i \le 10^9\)。
题目链接：https://www.luogu.com.cn/problem/P1842

思路：

本题我们刚拿到题，我们可以先举行模拟，我们可以界说一个结构体，存储奶牛的两个性质，力量和重量。一开始并没有什么太好的思路去计算最小的压扁指数，但是我们可以凭直觉猜想一下，我们要使得这一群奶牛当中，被压得最扁的奶牛的压扁指数尽可能的小，那么我们是不是就是要让最扁的那头奶牛的上面的全部牛的体重之和尽可能的小，并且让这头牛的力量尽可能的大，对吧？
以是说我们最低的压扁指数不仅仅与体重有关，也与牛的力量有关，以是说我们在采取排序计谋的同时，我们不可以大概仅仅根据体重或者是根据力量这一个元向来排序，我们一定要联合两个属性来排序，我们不妨猜想根据体重和力量的某种组合方式来举行排序，可以是重量与力量之差来排序，也可以是力量与重量之和来排序，只要我们证明，我们以某种排序规则下得到的总压扁指数是最小的，那么我们就成功证明了我们方案的可行性，对吧？

贪心计谋的证明：

<ol>
我们不妨先猜想按照力量和重量之和来排序，力量与重量之和小的排前面，反之则排背面。那么我们就必要证明，在这种排序规则之下，我们得到的总压扁指数就是最小的总压扁指数我们假设第i头牛它的压扁指数是总压扁指数，那么它前面全部牛的总重量是\(w_1\)+\(w_2\)+....w(i-1),此时的总压扁指数为w1+w2+....+w(i-1)-si,那么我们怎样去证明这个压扁指数就是最小的呢？我们可以试着交换任意两行奶牛，好比我们让第i头奶牛与第i-1头奶牛交换，那么此时的总压扁指数就变成了w1+w2+...wi-s(i-1),我们只必要证明 w1+w2+..w(i-1)-si> a.s; } sort(a + 1, a + 1 + n, compare);//答案先最任意初始化为一个最小值 int res = -2e9; int t = 0; for (int i = 1; i

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4