20分紧急求助,大佬们快来瞧瞧!
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
long long t;
long long z;
};
long long l,n,m;
long long a[50001];
bool v[50001];
node c[50001];
bool cmp(node x,node y)
{
return x.t<y.t;
}
int main()
{
cin>>l>>n>>m;
for(long long i=1;i<=n;i++)
{
cin>>a[i];
c[i].t=a[i]-a[i-1];
c[i].z=i;
}
a[n+1]=l;
c[n+1].t=a[n+1]-a[n];
c[n+1].z=n+1;
sort(c+1,c+n+2,cmp);
for(long long i=1;i<=n+1;i++)
{
if(m==0)
{
break;
}
if((v[c[i].z-1]==false&&c[i].z-1!=0)&&(v[c[i].z+1]==false&&c[i].z+1!=n+2))
{
if(a[c[i].z]-a[c[i].z-1]>a[c[i].z+1]-a[c[i].z])
{
m--;
c[c[c[i].z-1].z].t=a[c[i].z]-a[c[i].z-2];
c[i].t=1e18;
a[c[i].z-1]=a[c[i].z];
v[c[i].z-1]=true;
}
else
{
m--;
c[i].t=a[c[i].z+1]-a[c[i].z-1];
c[c[c[i].z+1].z].t=1e18;
a[c[i].z]=a[c[i].z+1];
v[c[i].z]=true;
}
}
else
{
if(v[c[i].z-1]==false&&c[i].z-1!=0)
{
m--;
c[c[c[i].z-1].z].t=a[c[i].z]-a[c[i].z-2];
c[i].t=1e18;
a[c[i].z-1]=a[c[i].z];
v[c[i].z-1]=true;
}
else
{
if(v[c[i].z+1]==false&&c[i].z+1!=n+2)
{
m--;
c[i].t=a[c[i].z+1]-a[c[i].z-1];
c[c[c[i].z+1].z].t=1e18;
a[c[i].z]=a[c[i].z+1];
v[c[i].z]=true;
}
}
}
}
long long ans=1e18;
for(long long i=1;i<=n+1;i++)
{
ans=min(ans,c[i].t);
}
cout<<ans;
return 0;
}