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\) ）
...
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.uj5u.com/qita/552428.html
標籤：其他
上一篇：程式員的十級孤獨，你體會過幾級
下一篇：返回列表