今天是因為David Lee正好講這個題的類似題，我才做了一下。
本題是world final 2016的一道水……
題目地址如下
http://www.lydsy.com/JudgeOnline/problem.php?id=4619.
這道題目讓我們求為格式化所有硬盤所需要買的最小的額外空間。
這道題目很容易能看出來是一道貪心題目（據David Lee說還有一種做法是二分+貪心，不過qdez的師天碩stonepage和我Icontofig都覺得二分+貪心有些麻煩，然而stonepage不打算寫，那就由我來寫這一篇題解報告）。
那我們該怎麼貪心呢？
第一種想法：我們看格式化後與格式化前的差值的大小來拍一遍序，然後加起來（剩余空間）看看最後我們需要多少額外空間（剩余空間是負數）。這個想法很容易被Hack掉，自己手寫一組加起來大於0的就可以Hack，因為你一開始的磁盤空間是0
第二種想法：我們先把格式化後與格式化前的差值大於0的加在一起，然後再根據每個磁盤的a值升序操作剩下的。這個也很容易hack掉，比如突然就來了一個格式化前空間非常大的，這種做法就懵逼了。
第三種想法：那我把第二種想法倒過來，行不行呢？顯然不行，有些數據隨隨便便就可以hack掉你。
那應該怎麼做？
正解：
我們對於輸入的數據進行預處理，把格式化後與格式化前的差值大於0的放在一個結構體裡面，把小於0的放在一個結構體裡。
先處理大於0的，對其根據b值進行升序排列，然後模擬過程（設一開始的剩余空間為0），用sum記錄過程中出現的最小負值，再用ans記錄剩余空間（就是待會兒程序裡面的co）。
再處理小於0的，同上操作（不過這時候剩余空間不是0了，上面操作已經更改過了）；
然後sum的絕對值就是我們想要的答案啦！具體證明明天我再問問stonepage；
具體代碼如下
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6 #include <cstdlib>
7 using namespace std;
8 typedef long long LL;
9 const int maxn = 1000005;
10 struct SD{
11 LL a,d;
12 }p[maxn];
13 struct counter{
14 LL a,b,co;
15 }pluss[maxn],dece[maxn];
16 bool cmp1(counter a,counter b){
17 return a.b < b.b;
18 }
19 bool cmp2(counter a,counter b){
20 return a.a > b.a;
21 }
22 LL n,ans,sum,now1,now2;
23 LL get_num(){
24 LL num = 0;
25 char c;
26 bool flag = false;
27 while((c = getchar()) == ' ' || c == '\n' || c == '\r');
28 if(c == '-')flag = true;
29 else num = c - '0';
30 while(isdigit(c = getchar()))
31 num = num * 10 + c - '0';
32 return (flag ? -1 : 1) * num;
33 }
34 void init(){
35 memset(p,0,sizeof(p));
36 memset(pluss,0,sizeof(pluss));
37 memset(dece,0,sizeof(dece));
38 now1 = now2 = 0;
39 }
40 int main(){
41 init();
42 n = get_num();
43 for(int i = 1;i <= n;++i){
44 p[i].d = get_num();
45 p[i].a = get_num();
46 if(p[i].a >= p[i].d){
47 pluss[++now1].a = p[i].a;
48 pluss[now1].b = p[i].d;
49 pluss[now1].co = p[i].a - p[i].d;
50 }
51 else{
52 dece[++now2].a = p[i].a;
53 dece[now2].b = p[i].d;
54 dece[now2].co = p[i].a - p[i].d;
55 }
56 }
57 sort(pluss+1,pluss+now1+1,cmp1);
58 sort(dece+1,dece+now2+1,cmp2);
59 for(int i = 1;i <= now1;++i){
60 sum = min(sum,ans - pluss[i].b);
61 ans += pluss[i].co;
62 }
63 for(int i = 1;i <= now2;++i){
64 sum = min(sum,ans - dece[i].b);
65 ans += dece[i].co;
66 }
67 printf("%lld\n",abs(sum));
68 return 0;
69 }
如果大家對我的博客有所意見，請通過我的郵箱聯系我，謝謝。
