我的PAT系列文章更新重心已移至Github，歡迎來看PAT題解的小伙伴請到Github Pages瀏覽最新內(nèi)容骚露。此處文章目前已更新至與Github Pages同步蓝纲。歡迎star我的repo绘搞。
題目
給定一段一段的繩子够委，你需要把它們串成一條繩。每次串連的時候肃叶，是把兩段繩子對折蹂随，再如下圖所示套接在一起。這樣得到的繩子又被當成是另一段繩子因惭，可以再次對折去跟另一段繩子串連岳锁。每次串連后，原來兩段繩子的長度就會減半蹦魔。
給定 段繩子的長度激率，你需要找出它們能串成的繩子的最大長度。
輸入格式：
每個輸入包含 1 個測試用例勿决。每個測試用例第 1 行給出正整數(shù) (
)乒躺；第 2 行給出
個正整數(shù)，即原始繩段的長度低缩，數(shù)字間以空格分隔嘉冒。所有整數(shù)都不超過 。
輸出格式：
在一行中輸出能夠串成的繩子的最大長度咆繁。結(jié)果向下取整讳推，即取為不超過最大長度的最近整數(shù)。
輸入樣例：
8
10 15 12 3 4 13 1 15
輸出樣例：
14
思路
一開始以為是huffman編碼么介，其實不用那么麻煩娜遵。每次找到最小的兩個結(jié)成新繩子（求平均）即可蜕衡。
由于要從小到大來找繩子壤短，當然排序是首先想到的方法设拟。但是繩子的長度不超過10^4，所以既然最多的情況都要用int[10000]的數(shù)組久脯，不如巧妙地用它來記錄數(shù)量而不是長度纳胧，這樣就不需要排序，時間復雜度為O(N)帘撰。
最短的繩子不需要和之前最短的繩子求平均跑慕，但如果設初值為最短繩子的長度，就沒有這個特殊處理了摧找，第一個for循環(huán)就是做這個核行。
看出來了，25分的題要不是考驗數(shù)學能力的蹬耘，就是間接考察數(shù)據(jù)結(jié)構(gòu)和算法的芝雪。
代碼
最新代碼@github，歡迎交流
#include <stdio.h>
int main()
{
int l[10001] = {0}, N, i;
double length = 0;
scanf("%d", &N);
for(int j = 0; j < N; j++)
{
scanf("%d", &i);
l[i]++; /* record counts */
}
for(i = 0; i < 10001; i++) /* find the shortest, special case */
if(l[i])
{
length = i;
break;
}
for(; i < 10001; i++) /* make new ropes */
while(l[i]--)
length = (length + i) / 2;
printf("%d", (int)length);
return 0;
}
