P1842 奶牛玩杂技

题目描述

题目链接

思路

这道题目知道结论是比较好写的，关键是结论是怎样推出来的。

我们先只考虑相邻的两个奶牛，设这两个奶牛为 (a) 和 (b) ，这两个奶牛上面的奶牛总重量为 (W) ，所以我们考虑 (a) 在上面的情况和 (b) 在上面的情况。

(a) 在上面的情况：

(a) 的压扁指数为 (W-S_a) ， (b) 的压扁指数为 (W+W_a-S_b) 。

(b) 在上面的情况：

(b) 的压扁指数为 (W-S_b) ， (a) 的压扁指数为 (W+W_b-S_a) 。

我们如果想让 (a) 在 (b) 的上面比 (b) 在 (a) 的上面更优，就需要满足 (max(W-S_a,W+W_a-S_b) <max(W-S_b,W+W_b-S_a)) 。

但是直接比较是没有办法比较的。

让我们看一下由已知条件我们可以推出来什么。

(W-S_a<W+W_b-S_a) ，所以我们可以发现 (W-S_a) 不用和 (W+W_b-S_a) 和 (W-S_b) 比较。因为我们设 (W+W_b-S_a) 为 (max) ，那么直接就可以得出结论。如果设 (W-S_b) 为 (max) ，那么就有 (W-S_a<W+W_b-S_a<W-S_b) 。所以 (W-S_a<max(W-S_b,W+W_b-S_a))

所以现在我们只需要让 (W+W_a-S_b<max(W-S_b,W+W_b-S_a)) 就可以了。

(W+W_a-S_b>W-S_b) ，和上面的证明相似，我们可以证明 (W-S_b<max(W-S_a,W+W_a-S_b)) 。

所以不论怎样 (W+W_a-S_b) 和 (W-S_b) 是没有可能满足条件的，所以我们只能让

[ left{ egin{aligned} W+W_a-S_b<W+W_b-S_a \ W-S_b<W+W_b-S_a end{aligned} ight. ]

解得 $$S_a+W_a<S_b+W_b$$

Code

#include<bits/stdc++.h>
#define pii pair<ll,ll>
#define mp make_pair
#define one first
#define two second
#define ll long long
using std::sort;
using std::pair;
using std::max;
using std::mp;
const int N=5e4+100;
const ll INF=9223372036854775807;
int n;
ll maxx=-INF;
pii id[N];
ll sum[N];
inline bool cmp(pii a,pii b) {return a.one+a.two<b.one+b.two;}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	scanf("%lld%lld",&id[i].one,&id[i].two);
	sort(id+1,id+n+1,cmp);
	for (int i=1;i<=n;i++)
	{
		maxx=max(maxx,sum[i-1]-id[i].two);
		sum[i]=sum[i-1]+id[i].one;
	}
	printf("%lld
",maxx);
	return 0;
}