BZOJ 4619 [Wf2016]Swap Space

题目大意

给你一堆硬盘，每个硬盘有一个旧的容量，这些硬盘都是满的。你可以买一个额外的存储设备加入存储池。每个硬盘格式化成新的文件系统之后可以得到一个新的容量，问这个额外的存储器最小的容量是多少。

这道题一看数据范围就是$O(NlogN)$的算法啊……考虑贪心。我的最开始的想法是：找一个容器使得它格式化比它小的盘，之后总值加一起大于最大的盘的原容量，之后就行啦~

事实证明我还是Too Yo......QwQ

看了Neither_Nor的题解终于明白了qwq

这道题把硬盘分为两种：1.搞完可以加冗余存储的。2.搞完冗余存储没了一部分的。对于可以增加的我们就按新容量从小到大排序，对于减少的我们就按旧容量从大到小排序，感性理解如下：我们希望进行操作之前尽可能少，其实就是让最后操作时候之后剩下的最少（因为总数据量是不变的），所以我们可以把它们分成两部分：一部分可以加冗余的就从小到大添加，一部分可以减冗余的就从大到小添加，按顺序进行操作就可以了。至于新的存储设备，我们把它转化成动态的，每次不符合要求就加一部分进去qwq

#include <cstdio>
#include <algorithm>
using namespace std;
long long n,pos,tmp,ans;
struct disk
{
	long long o,n,u;
}d[1000010];
bool cmp(disk tx,disk ty)
{
	if(tx.u==ty.u) return tx.u==1?tx.o<ty.o:tx.n>ty.n;
	return tx.u>ty.u;
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld",&d[i].o,&d[i].n);
		if(d[i].n-d[i].o>=0) d[i].u=true;
	}
	sort(d+1,d+n+1,cmp);
	pos=1;
	for(;d[pos].u;++pos)
	{
		if(tmp<=d[pos].o)
		{
			ans+=d[pos].o-tmp;
			tmp+=d[pos].o-tmp;
		}
		tmp+=d[pos].n-d[pos].o;
	}
	for(;pos<=n;++pos)
	{
		if(tmp<=d[pos].o)
		{
			ans+=d[pos].o-tmp;
			tmp+=d[pos].o-tmp;
		}
		tmp+=d[pos].n-d[pos].o;
	}
	printf("%lld\n",ans);
	return 0;
}