BZOJ 4619 Swap Space 解题报告

2018-06-17 23:58:06来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

今天是因为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 }

如果大家对我的博客有所意见,请通过我的邮箱联系我,谢谢。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:(转)OpenCV提取视频每一帧及将连续图片合成视频

下一篇:opencv 手写选择题阅卷 (二)字符识别