虽然贪心,但是没二分
查看原帖
虽然贪心,但是没二分
719140
only_joker楼主2023/10/14 19:14

30pts,如果告诉我思路不对和为什么不对,或者是帮我指正代码有什么不对,一关

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],sum=0,ans,l,minn=INT_MAX,o,k,d[100005],cinn=INT_MAX;
bool c[50005];
struct nd{
	int z;
	int j;
}b[100005];
bool cmp(nd x,nd y)
{
	return x.z<y.z;
}
int main(){
	cin>>l>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(i!=1&&i!=n) 
		{ 
			b[i].z=a[i]-a[i-1];
			d[i]=b[i].z;
			b[i].j=i;
			cinn=min(cinn,d[i]);
		} 
		else if(i==n)
		{
			b[i].z=l-a[i];
			d[i]=b[i].z;
			b[i].j=i;
			cinn=min(cinn,d[i]);
		}
		else 
		{
			b[i].z=a[i];
			d[i]=b[i].z;
			b[i].j=i;
			cinn=min(cinn,d[i]);
		} 
	}
	if(m>=n||n==0) 
	{
		cout<<l;
		return 0;
	}
	if(m==0)
	{
		cout<<cinn;
		return 0;
	}
//	for(int i=1;i<=n;i++)
//	{
//		cout<<b[i].z<<" ";
//	}
	sort(b+1,b+n+1,cmp);
//	for(int i=1;i<=n;i++)
//	{
//		cout<<b[i].j<<" "<<b[i].z<<endl;
//	}
	for(int i=1;i<=m;i++)
	{
		c[b[i].j]=true;
	}

	for(int i=1;i<=n;i++)
	{
		if(c[i]==false)
		{
			o=i-1;
			sum+=d[i];
			while(1)
			{
				if(c[o]==true) 
				{
					sum+=d[o];
					o--;
				}
				else break;
			}
			minn=min(minn,sum);
//			cout<<sum<<" ";
		}
		sum=0;
	}
	cout<<minn;
}
2023/10/14 19:14
加载中...