自动搬运

查看原文

来自洛谷，原作者为

	Aw顿顿 直须看尽洛城花，始共春风容易别

搬运于2025-08-24 22:32:00，当前版本为作者最后更新于2021-07-11 11:09:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

乍一看，好像有很多个变量，要在这些变量中得到答案没有那么直观。但是如果我们关注题目“令 $S-(A_{\max}-A_{\min})$ 最大” 这一要求，我们不难发现，当 $A_{\max}$ 和 $A_{\min}$ 这一范围确定之后，我们要尽可能把这一范围内的所有展品全部带走，这样才能保证 $S$ 尽可能大，从而保证在 $(A_{\max}-A_{\min})$ 确定的情况下整体尽可能大。

那我们是不是应该要枚举 $\max$ 和 $\min$ 值呢？实际上这种思路是可行的，在 $O(n\log n)$ 排序使得价值按序排列之后，枚举复杂度达到了 $O(n^2)$ 级别，这样的时间复杂度还不够优秀。

所以我们考虑只枚举 $\max$，在确定一个 $A_i$ 作为最小值之后，我们考虑把这个状态转移到下一个数，试图找出他们的关系。在从 $A_i$ 转化到 $A_{i+1}$ 之后，我们所求的目标值的变化为 $B_{i-1}-(A_i-A_{i+1})$，这应该是容易理解的。而实际上如果我们要连贯地将状态进行转移以方便枚举，我们就可以进行一步预处理，令：

这样我们就可以在常数时间内实现状态的转移，鉴于复杂度瓶颈在于排序部分的 $O(n\log n)$，而这个复杂度已经足以通过本题，于是不继续深入考量。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct num{
	int sz,val;
	bool operator <(const num &temp)const{
		return sz<temp.sz;
	}
}a[500005];
int n,f[500005],ans,mx;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].sz>>a[i].val;
	sort(a+1,a+n+1);
	for(int i=1;i<n;i++)
		f[i]=a[i].val-a[i+1].sz+a[i].sz;
	for(int i=1;i<=n;i++){
		int t=a[i].val;
		ans=max(ans,t+mx);
		mx=max(mx+f[i],(long long)0);
	}cout<<ans<<endl;
	return 0;
 }