PAT_A1125#Chain the Ropes

Source:

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

• 哈夫曼树
• 贪心

Attention:

• 依次把最小的结点相加即可
• a1 < a2 < a3, 则（a1+a2）/2 < a3

Code:

 /*

 Data: 2019-08-13 19:44:48

 Problem: PAT_A1125#Chain the Ropes

 AC: 14:23

 题目大意：

 两段绳子结在一起后长度减半

 输入：

 给出N段绳子及其长度

 输出：

 最大长度

 */

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int M=1e4+;

 int main()

 {

 #ifdef ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif // ONLINE_JUDGE

     int n,r[M];

     scanf("%d", &n);

     for(int i=; i<n; i++)

         scanf("%d", &r[i]);

     sort(r,r+n);

     for(int i=; i<n; i++)

         r[] = (r[]+r[i])/;

     printf("%d", r[]);

     return ;

 }