SP27102 FN16SWAP - Swap Space 题解

题目链接：SP27102 FN16SWAP - Swap Space

题意：

你管理着一个拥有多个计算机的大型集群，这些计算机上的硬盘使用各种不同的文件系统类型存储数据。最近，你决定将所有文件系统统一为相同类型。这是一个相当大的挑战，因为所有的硬盘目前都在使用中，它们都装满了重要数据，而且你不能承受任何数据丢失的风险。此外，将一个硬盘重新格式化为新的文件系统可能会显著改变其容量。为了使重新格式化成为可能，你将不得不购买一个额外的硬盘。显然，你希望通过尽量减小额外存储的大小来节省费用。

你可以以任何顺序重新格式化硬盘。在重新格式化一个硬盘之前，你必须将该硬盘上的所有数据移动到一个或多个其他硬盘上，必要时可以进行数据的分割。在一个硬盘重新格式化后，你可以立即开始使用它来存储来自其他硬盘的数据。并不需要将所有数据放在它们最初所在的硬盘上——事实上，如果某些硬盘在新的文件系统中具有较小的容量，这样做甚至可能是不可能的。同时，一些数据可能会被放在额外的硬盘上。

举个例子，假设你有四个硬盘 $A$、$B$、$C$ 和 $D$，它们的容量（旧文件系统）分别为 $6$、$1$、$3$ 和 $3$ $\text{GB}$。在新的文件系统下，它们的容量变为 $6$、$7$、$5$ 和 $5$ $\text{GB}$。如果你只购买了 $1$ $\text{GB}$ 的额外空间，你可以将硬盘 $B$ 上的数据移动到这里，然后重新格式化硬盘 $B$。现在，你在硬盘 $B$ 上有 $7$ $\text{GB}$ 的空闲空间，所以你可以将硬盘 $A$ 上的 $6$ $\text{GB}$ 数据移动到这里，并重新格式化硬盘 $A$。最后，你将来自硬盘 $C$ 和 $D$ 的总共六个$\text{GB}$的数据移动到硬盘 $A$ 上，并重新格式化硬盘 $C$ 和 $D$。

输入格式：

多个测试用例，直到输入结束为止。对于每个测试用例：

输入以包含一个整数 $n$（$1 \le n \le 10^6$）的行开始，表示你的集群中的硬盘数量。接下来的 $n$ 行描述每个硬盘的容量，每行包含两个整数 $a$ 和 $b$，其中 $a$ 是旧文件系统下的容量，$b$ 是新文件系统下的容量。

所有容量以$\text{GB}$为单位，并满足 $1 \le a, b \le 10^9$。（一千个PB应该足够大了，对吧？）

输出格式：

对于每个测试用例，显示必须购买的额外容量（以$\text{GB}$为单位），以重新格式化硬盘。

依稀记得 Roundgod 老师说过的，贪心题，通常考虑两个不同元素，会优先选哪个。

我们先来考虑 $x \le y$ 的元素。如果 $x$ 相同，那么选哪个都一样。如果 $y$ 相同，肯定选 $x$ 小的。

然后考虑 $x > y$ 的情况。如果 $x$ 相同，不确定。如果 $y$ 相同，肯定选 $x$ 小的。

看上去我们没法确定两个 $x$ 相等时的顺序，但是 $y$ 的角度似乎还有路可走。

设两个元素 $y_1 > y_2$ 。可以证明，如果先吃掉 $y_1$ 再吃掉 $y_2$ 不够时，即使先吃 $y_2$ 也不可能够。

证明：设钱数为 $t$ ，根据描述有 $t - (x_1-y_1) < x_2$ ，则 $t-(x_1-y_2) < x_2$ 即 $t-(x_2-y_2) < x_1$ $\square$

反之，先吃 $y_2$ 的决策用脚想想都知道有反例。所以我们一定会优先选 $y$ 大的。

因此我们只需要把 $x\le y$ 的按 $x$ 从小到大排序，$x > y$ 的按 $y$ 从大到小排序，然后扫一遍就好啦。

对了，关于 $x>y$ 的情况，还有一种理解方式，就是比较难想到：

考虑“时间倒流”，由减少变为增加，并根据 $x\le y$ 的贪心策略得知此时加容量时要按 $y$ 从小到大排序

时间复杂度 $\mathcal{O}(n \log n)$

代码：（三倍经验喵~）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
#define Fi first
#define Se second

pii a[N],b[N];
void solve(int n)
{
    int cnt1 = 0, cnt2 = 0;
    for(int i = 1, x,y; i <= n; i++)
    {
        if(cin >> x >> y, x > y) { 
            b[++cnt2] = make_pair(x, y); 
        } else { a[++cnt1] = make_pair(x, y); }
    }
    sort(a + 1, a + 1 + cnt1, [](pii x, pii y) { return x.Fi < y.Fi; });
    sort(b + 1, b + 1 + cnt2, [](pii x, pii y) { return x.Se > y.Se; });
    // int p = 0, k = 1; while(k) {
    //     if(!check(p + k)) { p += k, k <<= 1;} else k >>= 1;
    // }
    int res = 0, sum = 0; // 检查超支额度喵~
    for(int i = 1; i <= cnt1; i++) {
        up(res, a[i].Fi - sum), sum += a[i].Se - a[i].Fi;
    }
    for(int i = 1; i <= cnt2; i++) {
        up(res, b[i].Fi - sum), sum += b[i].Se - b[i].Fi;
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; while(cin >> n) solve(n);
    return 0;
}