[CSP-S模拟测试]:格式化（贪心）

题目传送门（内部题105）

输入格式

　　每组数据第一行一个正整数$n$，表示硬盘块数，接下来$n$行，每行两个正整数，第一个正整数为硬盘格式化前的容量，第二个正整数为格式化之后的容量。

输出格式

　　对每组数据输出一行一个正整数表示答案。

样例

样例输入1：

4
6 6
1 7
3 5
3 5

样例输出1：

样例输入2：

4
2 2
3 3
5 1
5 10

样例输出2：

数据范围与提示

样例解释：

　　第一组数据中，先将第二块硬盘的数据存放到容量为$1$的额外硬盘上再进行格式化，其容量变为$7$，之后将第一块硬盘的数据保存到第二块硬盘上，格式化第一块硬盘，最后将剩下两块硬盘的数据保存到第一块硬盘上再进行格式化。
　　第二组数据中，至少需要大小为$5$的额外空间才能格式化最后一块硬盘，而格式化最后一块硬盘后其它硬盘的内容都可以被保存然后格式化，故答案为$5$。

数据范围：

　　对于前$30\%$的数据，$n\leqslant 10$。
　　对于另外$20\%$的数据，格式化后硬盘的容量均大于格式化前的硬盘容量。
　　对于前$85\%$的数据，有$n\leqslant 1,000$。
　　对于$100\%$的数据，$1\leqslant n\leqslant 1,000,000$，输入中所有的数都是不超过$1,000,000,000=1,000^3$的正整数。

题解

考虑贪心。

为了保证代价最小，肯定是要让最后没有被用的硬盘空间最小。

考虑先收益再花费，一定是先格式化空间会变大的，然后再格式化空间会变小的一定不劣。

那么现在分开讨论这两种硬盘。

先来考虑格式化之后空间会变大的，先格式化格式化之前空间最小的一定不劣，因为我们会花费最小在每一块硬盘上，然后用它带来的贡献去弥补下一块硬盘。

再来考虑格式化之后空间会变小的，因为格式化这些硬盘的总代价不变，所以尽可能让最后没有被用的硬盘空间小，也就是格式化之后最小的硬盘一定放在最后；接着考虑前面的硬盘，因为最后的硬盘已经固定，就可以不考虑它，那么剩下的硬盘中格式化之后空间最小的一定放在最后；一直继续下去，也就是说按格式化之后硬盘的空间从大到小格式化一定不劣。

那么我们就能轻松解决此题了。

时间复杂度：$\Theta(n\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int a,b;}e[2000001],q1[2000001],q2[20000001];

int n,t1,t2;

long long ans,now;

bool cmp1(rec a,rec b){return a.a<b.a;}

bool cmp2(rec a,rec b){return a.b>b.b;}

int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d%d",&e[i].a,&e[i].b);

		if(e[i].a<=e[i].b)q1[++t1]=e[i];

		else q2[++t2]=e[i];

	}

	sort(q1+1,q1+t1+1,cmp1);

	sort(q2+1,q2+t2+1,cmp2);

	for(int i=1;i<=t1;i++)

	{

		now-=q1[i].a;

		if(now<0)

		{

			ans-=now;now=q1[i].b;

		}

		else now+=q1[i].b;

	}

	for(int i=1;i<=t2;i++)

	{

		now-=q2[i].a;

		if(now<0)

		{

			ans-=now;now=q2[i].b;

		}

		else now+=q2[i].b;

	}

	printf("%lld",ans);

	return 0;

}

rp++

巴特西