P6236 [COCI2010-2011#1] LJUTNJA题解

· · 题解

题目传送门

更好的阅读体验

Part 1 题目分析

贪心！！！

本题等价于将一个数分成 n 个数使它们的平方和尽量小即可。我们可以通过大量数据验证，当所有数尽可能相同时平方和最小。

例如 17 分成 3 份，分成 5 6 6 最合适。

第一个人分配 \lfloor\dfrac{17}{3}\rfloor=5 个，第二个人分配剩余的平均数 \dfrac{12}{2}=6 个，第三个人分配剩余的平均数 \dfrac{6}{1}=6 个。

Part 2 大坑

每个人分配的数目除了受平均数限制，还受他需求的糖果限制，不能超过他需求的糖果数目。所以我们还要将原来的 a_i 排序后一个个扫，若存在需要数比平均数小则更新答案和平均数，最后再将答案加上。

Part 3 代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int z[1<<17];
int main() {
  cin>>m>>n;
  long long sum=-m;
  for(int i=0;i<n;i++){
    cin>>z[i];
    sum+=z[i];
  }

//下面把sum分解成n个整数，使得平方和尽可能小。
  sort(z,z+n);
  long long ans=0;
  for(int i=0;i<n;i++){
    long long w=min(1LL*z[i],sum/(n-i));//剩余的平均数不能超过第i个人的糖果数目
    ans+=w*w;
    sum-=w;
  }
  cout<<ans<<endl;
  return 0;//完结撒花～～
}

AC记录

我的博客～～

by 2021.11.28 我的第四篇题解。