[ICPC2016 WF]Swap Space
题面翻译
你有 \(n\)个硬盘\((n\leqslant10^{6})\) ，现在需要对所有硬盘进行格式化。格式化后，第 \(i\) 个硬盘的容量会由原来的 \(a_{i}\) 变为 \(b_{i}\)。由于容量的改变，你需要购买硬盘容量来实现数据转移。数据可以分段转移，如把大小为 \((a+b)\ G\) 的数据分别存放在两个硬盘中，一个存 \(a\ G\) 一个存 \(b\ G\) 。一个硬盘被格式化后可以直接使用。求购买额外容量的最小值。
样例 #1
样例输入 #1
4
6 6
1 7
3 5
3 5
样例输出 #1
1
样例 #2
样例输入 #2
4
2 2
3 3
5 1
5 10
样例输出 #2
5
提示
Time limit: 5000 ms, Memory limit: 1048576 kB.
International Collegiate Programming Contest (ACM-ICPC) World Finals 2016
贪心
首先，硬盘更改后新系统后空间扩大的先进性，不变的居中，变小的后进性
1、扩大的，要先选初始空间小的，这样花费小，空间扩大后说不定就能存储初始空间大的了。这样通过空间扩大的硬盘可以积累一定的空间。
2、空间不变的无所谓，我是先进性的初始空间小的
3、空间缩小的，应该先选择缩小后空间较大的，这样可以用来存储后面空间较大的。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct node
{
int a,b,bz;
void work()
{
if(a>b)bz=1;
else if(a<b)bz=-1;
else bz=0;
}
};
node sz[maxn];
bool cmp(node x,node y)
{
if(x.bz!=y.bz)return x.bz<y.bz;
else
{
if(x.bz<0)return x.a<y.a||(x.a==y.a&&x.b>y.b);
else if(x.bz==0)return x.a<y.a;
else return x.b>y.b||(x.b==y.b&&x.a<y.a);
}
}
long long ans,cur;
int n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&sz[i].a,&sz[i].b);
sz[i].work();
}
sort(sz+1,sz+1+n,cmp);
for(int i=1;i<=n;++i)
if(cur<sz[i].a)
{
ans+=sz[i].a-cur;
cur=sz[i].b;
}
else
{
cur+=sz[i].b-sz[i].a;
}
cout<<ans<<endl;
return 0;
}