[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;
}
0 条评论