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;
}