A40833. 区间移位
填空题
困难
知识点
题目描述
区间移位
题目描述
参考答案
#include <bits/stdc++.h>
using namespace std;
int n;
struct section
{
int l;
int r;
}s[10005];
bool cmp(section a,section b)
{
if(a.r!=b.r)return a.r<b.r;
else return a.l<b.l;
}
bool check(int mid)
{
int i;
int pos=0;//pos记录当前已经填好的区间的最末端
bool vis[10005]={0};
while(1)
{
bool find=false;
for(i=1;i<=n;i++)
{
if(vis[i])continue;
if(s[i].l>pos)//当前区间需要往左靠拢
{
if(s[i].l-pos>mid)//这一段不能满足
{
find=false;
}
else
{
pos=s[i].r-(s[i].l-pos);
vis[i]=1;
find=true;
}
}
else if(s[i].l==pos)
{
pos=s[i].r;
vis[i]=1;
find=true;
}
else
{
if(pos-s[i].l<=mid)
{
pos=s[i].r+(pos-s[i].l);
vis[i]=1;
find=true;
}
else
{
if(s[i].r+mid>pos)
{
pos=s[i].r+mid;
vis[i]=1;
}
find=true;
}
}
}
if(pos>=20000)return true;
if(!find)break;
}
//这里别忘记改
return false;
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
{
scanf("%d%d",&s[i].l,&s[i].r);
s[i].l*=2;
s[i].r*=2;
}
sort(s+1,s+n+1,cmp);
int left=0,right=20000,mid,ans=0;
while(left<right)
{
mid=(left+right)/2;
if(check(mid))
{
right=mid;
}
else left=mid+1;
}
ans=left;
if(ans%2==0)
{
cout<<ans/2;
}
else
{
double aans=ans/2.0;
printf("%.1lf",aans);
}
return 0;
}
上一题
下一题