[ICPC2016 WF]Swap Space

题目链接 https://www.luogu.com.cn/problem/P6927

题目描述

你有许多电脑，它们的硬盘用不同的文件系统储存数据。你想要通过格式化来统一文件系统。格式化硬盘可能使它的容量发生变化。为了格式化，你需要买额外的硬盘。当然，你想要买容量最小的额外储存设备以便省钱。你可以按任意顺序格式化硬盘。格式化之前，你要把该硬盘上所有数据移到一个或更多的其他硬盘上（可以分割数据）。格式化后，该硬盘可以立刻开始使用。你没有必要把数据放到它原来所在的硬盘上。数据也可以被放到你额外买的硬盘上。举个例子，假设你有4个硬盘A、B、C、D，容量分别为6、1、3、3(GB)。新的文件系统下，它们的容量变为6、7、5、5(GB)。如果你只买1GB额外空间，你可以把B硬盘的数据放过去然后格式化硬盘B。现在你的B硬盘有7GB容量了，那么你就可以把A的数据放过去然后格式化A，最后把C、D的数据放到A上，再格式化C和D。

Solution

= = 我自己想的二分，然后发现队友贪心写的还特别短。。真的太强了，Orz

策略都一样，这里讲讲贪心吧。

把磁盘分为两类，一类 旧闪存 a 小于 新闪存 b ，另一类 旧闪存 a 大于 新闪存 b

显然第一类应该放在前面，这样处理第一类的时候就可以源源不断增加闪存，如果不够，在处理的时候直接给答案增加就好。

然后考虑第二类的处理顺序，这里我先想了两种，①先处理旧闪存小的，②先处理减少小的。发现都不对，然后蒙了一个 ③先处理新闪存大的，就对了。

这里尝试证明一下③的正确性

设有第二类磁盘 1 号和 2 号， a_1，b_1 和 a_2，b_2 。

满足a_1>b_1 a_2>b_2 不妨设 b_1>b_2

A=\max(a_1,a_1-b_1+a_2)
B=\max(a_2,a_2-b_2+a_1)

A 为按照 1,2 顺序处理时，所需要空间的最大值，B 为按照 2,1 顺序处理时，所需要空间的最大值。

显然这个最大值越小，越能满足题目要求。即当 A<B 时，1 号放在 2 号前面，所需要的空间更小，更优

当 a_1<a_2 时，有 a_2>a_1>b_1>b_2 ，A=a_1-b_1+a_2，B=a_2-b_2+a_1 。A<B

当 a_1>a_2 ：

​ 若 b_1>a_2 ，则有a_1>b_1>a_2>b_2 ，A=a_1 ，B=a_2-b_2+a_1， A<B

​ 若 b_1<a_2 ，则有 a_1>a_2>b_1>b_2，A=a_1-b_1+a_2，B=a_2-b_2+a_1，A<B

故 b 大的放在前面更优秀。

贴一个队友简练的代码：

#include<bits/stdc++.h>
struct D{
    long long a,b;
    inline bool operator <(const D &cmp)const
    {
        if((b-a)*(cmp.b-cmp.a) <= 0)return b-a>cmp.b-cmp.a; 
        //如果比较起来，一个元素 新空间-旧空间>0 ，另一个元素 新空间-旧空间<0  ，那么第一个放去前面，第二个放去后面 
        return b>a?a<cmp.a:b>cmp.b;
        // 否则看是哪种情况，如果是 新空间-旧空间>0，则按照 旧空间小的排，如果是新空间-旧空间<0 则按照 新空间大的排 
    }
}d[1000000];
int main()
{
    int n,i;
    long long ans;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%lld%lld",&d[i].a,&d[i].b);
    std::sort(d,d+n);
    ans = d[0].a;
    for(i=1;i<n;i++)
    {
        d[i].a += d[i-1].a, d[i].b += d[i-1].b;
        if(ans < d[i].a-d[i-1].b)ans = d[i].a-d[i-1].b;
    }
    printf("%lld",ans);
    return 0;
}

再看看我长长的代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+10;
int n,t1,t2,t3;
ll l,r;
pair<int,int> a[N],b[N],c[N]; 
inline int read(){
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
}
bool check(ll x){
    for(int i=1;i<=t1;++i){
        x-=a[i].first;
        if(x<0) return 0;
        x+=a[i].second;
    }
    for(int i=1;i<=t2;++i){
        if(x>=-c[i].second){
            x-=-c[i].second+c[i].first;
        }
        else
            return 0;
    }
    return x>=0;
}
int main(){
    n=read();
    for(int i=1;i<=n;++i){
        int x,y;
        x=read(),y=read();
        if(x<=y) a[++t1]=make_pair(x,y);
        else {
            b[++t2]=make_pair(x,y);
            c[t2]=make_pair(-y,-x);
        }
        l+=x;
    }
    std::sort(a+1,a+1+t1);
    std::sort(b+1,b+1+t2);
    std::sort(c+1,c+1+t2);
    r=0,l++;
    while(l-1>r){
        ll mid = l+r>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%lld",l);
    return 0;
}