题解 P6236 【[COCI2010-2011#1] LJUTNJA】

· · 题解

前言 ：

题面传送门

博客食用体验更加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 ！