题目回看

题目理解

有$n$个数$a_1,a_2…a_n$,现在在这$n$个数中选择几个数减去某个值(所有减去值的和为$m$),使得剩下的数的平方的和最小。

分析

很明显,如果要使这些剩下的数平方和最小,就是要尽量剔除最大的几个数。也就是让$n$个数中的最大值最小,这是一个明显的贪心。

代码构造

首先我想到了桶排序,用$f_i$表示需求量为$i$的人数,接下来只需要从$\max (a_1,a_2…a_n)$循环到$1$,把糖分给当前的的$f_i$,如果糖没了直接跳出循环。

好在这题的数据不算变态,开一个大小为$5000005$完全够这题数据了。

代码

#include <iostream>
using namespace std;
#define ll unsigned long long	//unsigned long long改为long long也是可以的
ll f[5000005];					//这题数据手下留情了
ll n,m;
ll mx;							//储存n个数中的最大值
ll ans;
inline ll max(ll a,ll b){
	return a>b?a:b;
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;++i){
		int tmp;cin>>tmp;
		++f[tmp];
		mx=max(tmp,mx);
      //读入需求量,然后再把需求量为tmp的人数+1
	}
	for(ll i=mx;i>=1;--i){	//一直循环到解决只需要一颗糖的的人
		if(m>=f[i]){		//如果糖果够现在的人
			m-=f[i];		//减去分掉的糖果   
			f[i-1]+=f[i];	//把糖果分给这f[i]个人,这f[i]个人需求量变为i-1
			--mx;			//最大需求量减一
			if(!m)break;	//如果当前没糖果分了,就跳出循环
		}
		else if(m<f[i]){
			f[i]-=m;		//如果当前糖果不够现在的人,能给几个人是几个
			f[i-1]+=m;		//同理这些个人变为只需要i-1个糖果
			break;
		}
	}
	for(ll i=mx;i>=1;--i)	//从需求量最大的开始,平方后加到ans里
	ans+=f[i]*i*i;
	cout<<ans;
	return 0;
}

完结撒花✿

发表评论

邮箱地址不会被公开。