农民约翰的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
输入样例:
3
10 3
2 5
3 3
输出样例:
2
(贪心)
思路: 与国王游戏的贪心策略相似, 我们先分析
每头牛的危险值 = 他前面牛的w(重量值)之和 - 自身的s(强壮值)
要使每头牛的危险值最小,根据贪心思想:
-
自身w值越大应该放到底部(即减小上述式中的被减数)
-
自身s值越大应该放到底部(即增大上述式中的减数)
所以先 yy 出一种贪心做法 每头牛的(w + s)值越大应该排在后面,即升序排序(题见多了可能就会有这种题感)。
接下来进行数学分析证明:
牛 | 交换前 | 交换后 |
---|---|---|
i | i−1∑j=1wj−si | i−1∑j=1wj+wj+1−si |
i+1 | i∑j=1wj−si+1 | i−1∑j=1wj−si+1 |
交换前后其他牛的危险值不变
-
i之前的牛并不涉及牛i与i+1的重量值,
-
i+1之后的牛只涉及到牛i与i+1重量值的和,
所以分析交换前后这两头牛中最大的危险值即可。
将上述式子进行化简,每个式子减去 i−1∑j=1wj
得到如下式子
牛 | 交换前 | 交换后 |
---|---|---|
i | −si | wi+1−si |
i+1 | wi−si+1 | −si+1 |
由于s, w都是正数,wi−si+1>−si+1 , wi+1−si>−si
比较wi−si+1, wi+1−si即可
-
当wi−si+1>=wi+1−si,即 wi+si>=wi+1+si+1时, 交换后更优
-
当wi−si+1<wi+1−si,即 wi+si<wi+1+si+1时, 交换前更优
所以得到做法: 按每头牛的 w + s 进行排序,
当存在逆序时就进行交换(即升序排序),
然后根据题意算出每头牛的危险值记录其中的最大值即可
代码:
#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;
}
其他牛的危险值显然不变,所以分析交换前后这两头牛中最大的危险值即可。
分析确实很清楚,但是还是再加一句话:第 i 头牛在第 i + 1 头牛的上面
确实,我也在这里卡了
这种结论是怎么想出来的,很好奇
这道题目对每一头牛来说最大危险系数不应该是它在最底下的时候吗?
是的,但是根据我的理解要保证最大危险系数最小,这个牛放在哪里还需要考虑这个牛的质量,而仅考虑吧一头牛的风险系数没有考虑这个牛的质量
为什么 为什么 比较wi−si+1wi−si+1,wi+1−siwi+1−si 即可 ?
因为题目的要求是最大值中风险值最小
即交换后的max(wi+1−si,−si+1) 需要小于等于 交换前的max(−si,wi−si+1)
由此可推得如上不等式
请问怎么推?
我不理解?
题目要求的是最大风险值的最小可能值,在只有i和i+1两头牛的情况下:
最大风险值的范围是(-Si, Wi - Si+1, Wi+1-Si, -Si+1)
由于Si, Wi, Wi+1, Si+1的值均大于0
可得Wi - Si+1 > -Si+1, Wi+1-Si > -Si,即最大风险范围是 (Wi - Si+1, Wi+1-Si)
综上,比较 Wi - Si+1, Wi+1-Si两个值的大小就可以了
根据题意,只需要比较交换前后的风险最大值,这俩已经分别大于对方的另一个了,所以最后只需要比较这两个就可以了
按照 d = Si + Wi 的升序对奶牛进行排序并不能保证每头奶牛的风险值尽可能小。下面是一个简单的例子来说明这一点。
假设有两头奶牛 A 和 B,它们的重量分别为 Wa = 2 和 Wb = 3,强壮程度分别为 Sa = 4 和 Sb = 1。那么,我们有 Wa + Sa = 6 和 Wb + Sb = 4。
如果我们按照 d = Si + Wi 的升序对奶牛进行排序,那么奶牛 B 会排在奶牛 A 的下面。在这种情况下,奶牛 A 的风险值为 Wb - Sa = -1,奶牛 B 的风险值为 0。因此,最大风险值为 -1。
但是,如果我们将奶牛 A 放在奶牛 B 的下面,那么奶牛 A 的风险值为 0,奶牛 B 的风险值为 Wa - Sb = 1。因此,最大风险值为 1。
由于 -1 < 1,所以按照 d = Si + Wi 的升序对奶牛进行排序并不是最优的。
这个例子说明,按照 d = Si + Wi 的升序对奶牛进行排序并不能保证每头奶牛的风险值尽可能小。
您可以参考这个例子来理解这个问题。
newbing给的wi+si升序不成立的证明,我怎么感觉是对的
你理解反了,升序排列是让“奶牛 B 会排在奶牛 A 的下面”。
import java.util.*; public class Main{ public static void main(String[] args) { Scanner scan = new Scanner(System.in); List<PIIs> list = new ArrayList<PIIs>(); int n = scan.nextInt(); for(int i = 0;i < n;i++) { int w = scan.nextInt(); int s = scan.nextInt(); list.add(new PIIs(w + s,w)); } Collections.sort(list); int res = Integer.MIN_VALUE; int sum = 0;//记录危险值 for(PIIs item : list) { int w = item.getSecond(); int s = item.getFirst() - w; res = Math.max(res, sum - s); sum += w; } System.out.println(res); } } class PIIs implements Comparable<PIIs>{ private int first; private int second; public int getFirst() { return this.first; } public int getSecond() { return this.second; } public PIIs(int first,int second) { this.first = first; this.second = second; } @Override public int compareTo(PIIs o) { // TODO 自动生成的方法存根 return Integer.compare(first, o.first); } }
这个把所有代码框起来是怎么操作的大佬
跟打卡时一样的
good~
牛牛牛
//这题说到底,是不是就要是要摆列的牛尽量w大的放下面,w小的放上面啊 //类比到人,你说一个100斤的人和一个200斤的人,你觉得谁在上谁在下更稳一点?
算法题不能用现实来类比,你完全可以看到一个体重为99999999而力气为1的牛,也可以看到一个体重为1而力气为99999999的牛,那么排序就是个抽象的问题了:]
但是你说的特殊栗子啊,他这题是要贪心求最优解啊
牛牛牛
orz
太牛了啊大佬,给大佬跪一个orz
#include [HTML_REMOVED]
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int N = 1e5 + 5;
struct pos {
int w, s, val;
} a[N];
bool cmp(pos &x, pos &y) {
return x.val > y.val;
}
void solve() {
int n;
cin >> n;
long long ans = -1e18;
long long sum = 0;
for (int i = 1; i <= n; i) {
cin >> a[i].w >> a[i].s;
a[i].val = a[i].w + a[i].s;
sum += a[i].w;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i) {
ans = max(ans, sum - a[i].val);
sum -= a[i].w;
}
cout << ans;
}
int main() {
IOS;
int ;
_ = 1;
while (–)
solve();
return 0;
}
为什么危险值最大的不是最后一头牛?而是每一个都取max呀。友友们
还要考虑牛的强壮程度吧,风险值=取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值
如果最后一头牛强壮程度无限大,那么最后一头牛的风险值不一定是最大的
Orz
这样也可以的QAQ
#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N = 500010; int n; int w[N], s[N]; vector<pair<int, int>> a; int main(){ cin >> n; for(int i = 0; i < n; i++) cin >> w[i] >> s[i], a.push_back({w[i] + s[i], i}); sort(a.begin(), a.end()); int res = -s[a[0].second], aw = 0; for(int i = 0; i < n; i++) if(i){ aw += w[a[i - 1].second]; res = max(res, aw - s[a[i].second]); } cout << res; return 0; }
这个把所有代码框起来是怎么操作的
评论区支持markdown,你用```把将代码包起来就可以
和打卡那个一样的
Orz
#include <bits/stdc++.h> using namespace std; const int N = 5e4+10; using LL = long long; using PLL = pair<LL,LL>; #define x first #define y second PLL q[N]; int n; int main() { scanf("%d",&n); LL sum=0; for(int i=0;i<n;++i){ scanf("%ld%ld",&q[i].x,&q[i].y); sum+=q[i].x; } sort(q,q+n,[](const auto& a,const auto& b){ return a.x+a.y>b.x+b.y; }); LL res=-1e16; for(int i=0;i<n;++i){ sum-=q[i].x; res=max(res,sum-q[i].y); } cout<<res<<endl; return 0; }
这个把所有代码框起来是怎么操作的
Orz
大佬见多了,我就有深深的自卑感