BZOJ 4619/3709: [WF2016]Swap Space – [贪心]


题目传送门(BZOJ)

题解 :

BZOJ_3709 非常像
首先这些硬盘是可以分成两部分的 :
一部分格式化之后会使得空间变大, 一部分格式化之后会使得空间变小
肯定是先选择使得空间变大的格式化, 假设说现在选择某个变大的需要多购买 x,
那么在之前若选择过使得空间变小的硬盘, 只会使得需要的 x 更大 (还需要承担那个硬盘多出来的部分)
而若是先选择使得空间变大的格式化, 在 x 不变的情况下, 未来那个硬盘多出来的部分还可以存到这个硬盘变大的部分上
综上, 一定先选择变大的, 后选择变小的
那么如果两个硬盘都变大怎么选 :
设硬盘分别为 [a_1, b_1], [a_2, b_2] 其中 a_1
那么, 若先选择初始大的 a_2, 需要多买 a_2 这部分 , 到了 a_1 则不需要再多购买了
若先选择 a_1, 则只需要购买 a_2 – (b_1-a_1) 这么大, 要比上面的方式优秀
那么考虑如果之前剩了一些空间, 由于多出来的空间少, 按先选小的一定不会更差
故当两个硬盘都变大时, 按初始小的先选
再考虑当两个硬盘都变小时怎么选
按格式化之后空间大的先选, 因为前面的选完之后, 多出来的容量已经确定了, 我们目的就是让再多买的尽可能少
同样设硬盘为 [a_1, b_1], [a_2, b_2] 其中 a_1 > b_1, a_2 > b_2, b_1 > b_2
再设之前剩下的容量为 G
先买第一个再买第二个 : G-a_1+b_1-a_2
先买第二个再买第一个 : G-a_1+b_2-a_2
故前者更优

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 1001000;
struct DISK {
    int a, b;
    bool operator < (const DISK &A) const {
        if((a < b) != (A.a < A.b)) return (a < b) > (A.a < A.b);
        if( a < b) return a < A.a;
        else return b > A.b; 
    }
}a[N];
int main() {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i].a, &a[i].b);
    sort(a+1, a+n+1); long long ans = 0, sum = 0;
    for(int i = 1; i <= n; i ++ ) {
        ans = min(ans, sum-a[i].a);
        sum += (a[i].b-a[i].a);
    }
    printf("%lld\n", -ans);
    return 0;
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注