自动搬运

查看原文

来自洛谷，原作者为

	btng_smith666 AFOed

搬运于2025-08-24 22:18:52，当前版本为作者最后更新于2020-03-31 11:03:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言 ：

题面传送门

博客食用体验更加qwq

一道十分明显又常见的贪心题——

思路 ：

本题就是将一些糖果分配给几个幼儿园小盆友，每个小盆友有各自的期望值，如果没有达到期望值生气指数就会增加（生气指数=少得到糖果数的平方）,让你找到最优分配方案使得生气指数和最小

做法：先对 $a$ 数组进行从大到小降幂排序，然后从最大期望值开始循环 $m$ 颗糖果，每次循环判断一下最大值($maxx$)是否是 $a[qwq]$（$qwq$ 相当于一个临时变量），如果不是就将 $a[1]$ 赋值到最大值 $maxx$ 里，还原 $qwq$ 为 $1$ ，继续循环，如果 $maxx$ 和当前的 $a[qwq]$ 相等，就将 $qwq + 1$ 然后将数组中 $-1$ 继续往后进行，注意最后 $m$ 也要 $-1$，循环结束后直接用 $a$ 数组里存储的每个小盆友少得到的糖果数进行平方累加即可

代码 ：

#include<bits/stdc++.h>//Code by btng_smith666 juruo
using namespace std;
long long a[100001],ans,n,m,maxx,qwq=1;//注意开 long long 
bool cmp(long long x,long long y)//手打 cmp 
{
	return x>y;//降幂排列 
}
int main(qwq)//主函数 
{
	scanf("%lld%lld",&m,&n);
    for(int i=1;i<=n;i++)
    	scanf("%lld",&a[i]);
    sort(a+1,a+n+1,cmp);//先降幂排一下序 
    maxx=a[1];//将最大值赋成输入中 n 个孩子的最大期望值 
    while(m)//循环找出最优分配方法 
        if(a[qwq]!=maxx) 
            maxx=a[1],qwq=1;
        else  
        	a[qwq++]--,m--;
    for(int i=1;i<=n;i++)
		ans+=a[i]*a[i];//将少的颗数平方累加到最优方案里，注意这道题最后一个点成功把 STL math 库里的 pow 函数完美地卡死了 
    printf("%lld",ans);
    return 0;
}

后记 ：

本代码有防抄袭措施，但估计只要学过 C++ 就能轻易发现

大家如果觉得好的话就点个赞吧 qwq ！