分析
如果上来就给出w[i+1]+s[i+1]>=w[i]+s[i]
这样的决策无疑是玄学,那么这道题有什么自然的分析方法吗?
首先我们用数学语言描述这道题:(我们记从上到下牛的编号为1--n
)
那么我们要求的就是找出一种牛的排列方式,令$max(w_{1}+···+w_{i-1}-s_{i})$最小,记这个值为$val$。
为了求排序的方案,可以交换$i$,$i+1$牛的位置,看看满足什么等价条件,就可以使得交换之后$val$不比之前大。
下面求交换之后$val$不比之前大的等价条件:
(注意到交换$i$,$i+1$牛的位置不会影响其他牛的风险度,故只需考察这两头牛。)
交换前:
牛$i$:
$w_{1}+···+w_{i-1}-s_{i}$ $①$
牛$i+1$:
$w_{1}+···+w_{i-1}+w_{i}-s_{i+1}$ $②$
交换后:
牛$i$:
$w_{1}+···+w_{i-1}+w_{i+1}-s_{i}$ $③$
牛$i+1$:
$w_{1}+···+w_{i-1}-s_{i+1}$ $④$
$val$不比之前大,即$max(①,②)\geqslant max(③,④) $
下面的任务是求 $max(①,②)\geqslant max(③,④) $ 的等价条件:
注意到四个柿子式子都有$w_{1}+···+w_{i-1}$,同时删去不影响结果,故等价于:
$$max(-s_{i},w_{i}-s_{i+1})\geqslant max(w_{i+1}-s_{i},-s_{i+1})$$
若$-s_{i} > w_{i}-s_{i+1}$ , 但$-s_{i} < w_{i+1}-s_{i}$矛盾,故有$-s_{i} \leqslant w_{i}-s_{i+1}$
故上式进一步等价于:
$$ w_{i}-s_{i+1}\geqslant max(w_{i+1}-s_{i},-s_{i+1})$$
自然,$w_{i}-s_{i+1} > -s_{i+1}$
故上式进一步等价于:
$$ w_{i}-s_{i+1}\geqslant w_{i+1}-s_{i}$$
即
$$ w_{i}+s_{i}\geqslant w_{i+1}+s_{i+1}$$
至此,我们找到了交换之后$val$不比之前大的等价条件,这意味着当$ w_{i}+s_{i}\geqslant w_{i+1}+s_{i+1}$的时候,
交换$i$,$i+1$牛的位置$val$不比之前大,所以得到决策方案:$ w_{i}+s_{i}\leqslant w_{i+1}+s_{i+1}$,即从上到下满足:
$ w_{i}+s_{i}$值递增
因为代码实现很简单就不注释了^3^
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4+5;
struct node{
int w,s;
}a[N];
int n;
bool cmp(node a,node b){
return a.w+a.s<=b.w+b.s;
}
ll sum=0;
int ans=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].s;
sort(a+1,a+n+1,cmp);
ans=sum-a[1].s;
sum=a[1].w;
for(int i=2;i<=n;i++){
if(sum-a[i].s>ans) ans=sum-a[i].s;
sum+=a[i].w;
}
cout<<ans<<endl;
return 0;
}
upd: 2021.5.3
而事实上,如果无法理解 $max(-s_{i},w_{i}-s_{i+1})\geqslant max(w_{i+1}-s_{i},-s_{i+1})$ 以下的推导柿子,可以直接以这个柿子为排序依据(排序的时候符号反过来,因为原式表示的是交换后比原来好的情况)。
见代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4+5;
struct node{
int w,s;
}a[N];
int n;
bool cmp(node a,node b){
return max(-a.s, a.w-b.s)<max(-b.s, b.w-a.s);
}
ll sum=0;
int ans=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].s;
sort(a+1,a+n+1,cmp);
ans=sum-a[1].s;
sum=a[1].w;
for(int i=2;i<=n;i++){
if(sum-a[i].s>ans) ans=sum-a[i].s;
sum+=a[i].w;
}
cout<<ans<<endl;
return 0;
}
题解写的很棒,我肖某表示一下子就看懂了
关于 $$max(−s_{i},w_{i}−s_{i+1})⩾max(w_{i+1}−s{i},−s_{i+1})$$ 可以参考y总视频 https://www.acwing.com/video/317/ 10:00 ,把这四个数同时+ $$ s_{i} + s_{i+1}$$
嗯嗯,这样更好看些~
哈 对 你写的也很清楚! 我就是给自己note一下哈哈
题解很好,就是式子打错城柿子了哦
牛啊,数学证明牛逼
但是令$max(w_1+⋅⋅⋅+w_{i−1}−s_i)$这里的$1<=i<=n$,这是怎么保证全局的最大值最小的呢
这正是我们需要解决的,所以通过下面的排序最小化这个值
按照《进阶指南》的思想:每次调整减少$w_i+s_i>w_{i+1}+s_{i+1}$的逆序对都使答案更优,于是像冒泡排序那样交换排序得到的每个相邻$max(w_1+⋅⋅⋅+w_{i−1}−s_i,w_1+⋅⋅⋅+w_i−s_{i+1})$的最小值,而全局最大值就是这些相邻对最大值之一,于是全局最大值能够最小
是的,下面的排序分析也是在做类似的事
很好的
柿子
orz
严谨Orz
牛
风险值最大的不是最后一头牛吗?为什么还要从头遍历?
求的是总和
谢谢
谢谢大佬!
感谢
tql
请问意思是不是 满足
wi+si⩾wi+1+si+1
这样就可以通过发生交换而更新最优值,所以我们排序的时候按照wi+si<wi+1+si+1这个来排序 就能保证最优 其中i 在 i+1上方 是从上到下遍历的嗯嗯,所以
cmp
可以写成:好的谢谢大佬,tql
没事qwq~
66666
妙啊!!!!
妙啊!%%%
666
小于等于会出事的
对,谢谢qwq