底下的牛的强壮程度$S$越大越好
上面牛的重量和$W$越小越好(越重的放越下面)
=>
直觉是S[i]+W[i]
越大的放越下面
证:
贪心得到的答案≥最优解(根据最优解定义:所有排序方案的最小值)
贪心得到的答案≤最优解
如果不是按S[i]+W[i]
从小到大排序一定存在相邻i
和i+1
有$w_{i}+s_{i}>w_{i+1}+s_{i+1}$
- 可以发现此时交换第$i$头牛和第$i+1$头牛不影响$[0,i-1]$和$[i+2,n]$的风险
变化 | 第$i$个位置上的牛 | 第$i+1$个位置上的牛 |
---|---|---|
交换前 | $$w_1+…+w_(i-1)-s_i$$ | $$w_1+…+w_(i)-s_(i+1)$$ |
交换后 | $$w_1+…+w_(i-1)-s_(i+1)$$ | $$w_1+…+w_(i-1)+w_(i+1)-s_(i)$$ |
- 前$i-1$项减去
变化 | 第$i$个位置上的牛 | 第$i+1$个位置上的牛 |
---|---|---|
交换前 | $$-s_i$$ | $$w_(i)-s_(i+1)$$ |
交换后 | $$-s_(i+1)$$ | $$w_(i+1)-s_(i)$$ |
- 加上$s_{i}+s_{i+1}$
变化 | 第$i$个位置上的牛 | 第$i+1$个位置上的牛 |
---|---|---|
交换前 | $$s_(i+1)$$ | $$w_i+s_i$$ |
交换后 | $$s_i$$ | $$w_(i+1)+s_(i+1)$$ |
$$ w_i+s_i>s_i\\\\ w_i+s_i \geq w_(i+1)+s_(i+1)\\\\ w_i+s_i \geq max(s_i,w_(i+1)+s_(i+1))\\\\ 由w_{i}+s_{i}>w_{i+1}+s_{i+1} -> w_{i}+s_{i}>s_{i+1}-> w_{i}+s_{i}=max(s_(i+1),w_i+s_i)\\\\ max(s_(i+1),w_i+s_i) \geq max(s_i,w_(i+1)+s_(i+1))\\\\ max(交换前) \geq max(交换后)\\\\ 所有风险的最大值起码不会变大\\\\ 即只要w_{i}+s_{i}不是严格递增,则我们可以把他们变成递增的\\\\ 并且所有风险的最大值不会变大 $$
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=50010;
#define x first
#define y second
int n;
PII cow[N];
int main()
{
cin >> n;
for(int i=0;i<n;i++)
{
int w,s;
cin >> w >> s;
cow[i] = {w+s,w};
}
sort(cow,cow+n);
int res = -1e9,sum=0;
for(int i=0;i<n;i++)
{
int s;
s = cow[i].x-cow[i].y;
res = max(res,sum-s);//风险 = 上面的重量-当前的承受
sum+=cow[i].y;
}
cout << res;
return 0;
}
max表示是只是单个层,又不是两个层一起变小
大佬有markdown的源码吗?我想学习下
orz
orz
orz
S[i]+W[i]从小到大排序一定存在相邻i和i+1有wi+si>wi+1+si+1, 大佬这句话支撑在哪呀。为什么会有呢
如果不是按