[JOI2017/2018]美術展

题目大意：

有\(n(n\le5\times10^5)\)个物品，每个物品有两个属性：尺寸\(A_i\)和收益\(B_i\)。从中选取一个子集，总收益为\(\sum B_i-\max\{A_i\}-\min\{A_i\}\)。求总收益最大值。

思路：

将所有物品按照\(A_i\)排序，\(B_i\)前缀和记作\(S_i\)。答案相当于\(\max\{S_i-A_i+A_j-S_{j-1}\}\)。维护\(A_j-S_{j-1}\)前缀\(\max\)即可。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

typedef long long int64;

inline int64 getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int64 x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=5e5+1;

struct Node {

	int64 a,b;

	bool operator < (const Node &rhs) const {

		return a<rhs.a;

	}

};

Node v[N];

int64 sum[N];

int main() {

	const int n=getint();

	for(register int i=1;i<=n;i++) {

		v[i].a=getint();

		v[i].b=getint();

	}

	std::sort(&v[1],&v[n]+1);

	int64 max=0,ans=0;

	for(register int i=1;i<=n;i++) {

		sum[i]=sum[i-1]+v[i].b;

		max=std::max(max,v[i].a-sum[i-1]);

		ans=std::max(ans,sum[i]-v[i].a+max);

	}

	printf("%lld\n",ans);

	return 0;

}