U163898
题目
题目背景
栋栋参加比赛拿下了一等奖，老师奖励了很多糖果。
题目描述
一共有 \(m\) 种糖果，其中第i种糖果的数量为 \(m_i\) 。栋栋吃糖时会获得快乐值，并且他喜欢换着口味吃糖。当栋栋吃下第一个糖果时快乐值为 \(0\) ，接下来，每吃一个不同口味的糖果(与上一个糖不同)，快乐值就会增加 \(5\) 点，而连续吃下 \(k\) 个相同口味的糖果，快乐值就会减少 \(3*(k-1)\) 点。栋栋已经下定决心要吃完所有的糖果。现在他想知道如何安排吃糖的顺序才能使快乐值最大。请你求出最大快乐值。
输入格式
输入分两行
第一行输入整数 \(m\)
第二行输入 \(m\) 个整数，分别表示每种糖果的数量 \(m_i\) 。
输出格式
输出栋栋能获得的最大快乐值
输入输出样例
样例1
输入1
3
3 1 1
输出1
20
样例2
输入2
3
4 1 1
输出2
17
说明/提示
对于\(100\%\)的数据，有\(1<m\le1000\) ， \(1\le m_i≤10000\) ， \(1<m\le1000\)，\(1≤m_i≤10000\)。保证结果在int范围内。
题解
定义
此题是广义鸽巢原理的一道例题。
先说一下什么是鸽巢原理：
定义：如果 \(k+1\) 个或更多个物体放入 \(k\) 个盒子，那么至少有一个盒子包含了 \(2\) 个或更多的物体。此定理也被称为狄利克雷抽屉原理。
但是此题用到的是广义鸽巢原理。
定义：如果 \(N\) 个物体放入 \(k\) 个盒子，那么至少有一个盒子包含了至少 \(\left\lceil\dfrac{N}{k}\right\rceil\) 个物体。
举个例子，在100人中，至少有 \(\left\lceil\dfrac{100}{12}\right\rceil=9\) 个人的生日在同一个月。
看完题后，我们会发现，有许多东西我们都不需要。我们现在需要的是 \(N\) 和 \(k\) 。
用总糖果数量减去最大数量糖果类型可以得出其它糖果数量综合。
所以处理情况是这样的：
...
signed main(){
int m,md=0,ans=0,sum,a;
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&a);
ans+=a;
md=max(md,a);
}
ans-=md;
...
return 0;
}
当我们发现吃糖时不用减少快乐值时，即吃重复糖最多只吃一次时：
...
if(ans-md>=-1){
printf("%d",(ans+md-1)*5);
return 0;
}
...
当我们发现必须减少快乐值时：
如果不计损失的快乐值，那么就只有 \(ans*10\) 的快乐值了。
我们可以这么理解：
我们已经知道了其它类糖果总数量为 \(ans\) ，最大数量糖果类总数量为\(md\) ，所以我们把可以看作有 \(md-1\) 个盒子要放下 \(ans\) 个糖果。（关键思路）
所以代码就出来了，如果求总和会要用到等差数列公式： \(\frac{n(a+n)}{2}\) 。（注意此处等差数列公式是 \(1+2+...+n-1+n\) ）文章来源：https://www.toymoban.com/news/detail-443643.html
...
const int P1=ceil(md/(double)(ans+1));
const int P2=md/(ans+1);
const int P3=md%(ans+1);
sum-=3*((ans+1-P3)*(P2-1)*P2/2+P3*P1*(P1-1)/2);
printf("%d",sum);
...
代码（不建议看）
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cstdio>
using std::max;
signed main(){
int m,md(0),ans(0),sum,a;
scanf("%d",&m);
for(register int i(1);i<=m;i=-~i){scanf("%d",&a);md=max(md,a),ans+=a;}
ans-=md;
if(ans-md>=-1){
printf("%d",(ans+md-1)*5);
exit(0);
}
sum=ans*10;
const int P1=ceil(md/(double)(ans+1));
const int P2=md/(ans+1);
const int P3=md%(ans+1);
sum-=3*((ans+1-P3)*(P2-1)*P2/2+P3*P1*(P1-1)/2);
printf("%d",sum);
exit(0);
return 0;
}
后记：几年前的东西，看个乐子。文章来源地址https://www.toymoban.com/news/detail-443643.html
到了这里，关于中二羊专题：栋栋吃糖果的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
