题目传送门(BZOJ)

题解 :

BZOJ_3709 非常像
首先这些硬盘是可以分成两部分的 :
一部分格式化之后会使得空间变大, 一部分格式化之后会使得空间变小
肯定是先选择使得空间变大的格式化, 假设说现在选择某个变大的需要多购买 $x$,
那么在之前若选择过使得空间变小的硬盘, 只会使得需要的 $x$ 更大 (还需要承担那个硬盘多出来的部分)
而若是先选择使得空间变大的格式化, 在 $x$ 不变的情况下, 未来那个硬盘多出来的部分还可以存到这个硬盘变大的部分上
综上, 一定先选择变大的, 后选择变小的
那么如果两个硬盘都变大怎么选 :
设硬盘分别为 $[a_1, b_1], [a_2, b_2]$ 其中 $a_1 < b_1, a_2 < b_2, a_1 < a_2$
那么, 若先选择初始大的 $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 <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>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原创, 转载必须以链接形式注明>原文链接<