20分紧急求助,大佬们快来瞧瞧!
查看原帖
20分紧急求助,大佬们快来瞧瞧!
551894
lemon2021楼主2023/1/9 17:54

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;
}
2023/1/9 17:54
加载中...