一、题目描述
原题链接
Input Specification:
Output Specification:
Sample Input:
8 10 15 12 3 4 13 1 15
Sample Output:
14
二、解题思路
利用了贪心的思想，两条绳子要连起来，形成的新绳子的长度就是原来两段绳子之和的一半。现在给我们一些不同长度的绳子，要怎么样获得最长长度的绳子呢？考虑长度为1和15的两条绳子，得到的新绳子长度为8，那么与之前较长的绳子15的长度差就非常大，我们可以理解成绳子“损失”了，而长度为7和15的两段绳子，得到的新绳子长度为11，长度“损失”减小，也就是说，我们要尽量把短的绳子和短的绳子相连，长的和长的相连。理解这个思想，代码就很容易写出来了。
三、AC代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std
;
int main()
{
int N
, tmp
;
vector
<int> len
;
scanf("%d", &N
);
for(int i
=0; i
<N
; i
++)
{
scanf("%d", &tmp
);
len
.push_back(tmp
);
}
sort(len
.begin(), len
.end());
int ans
=0;
if(N
== 1) printf("%d", len
[0]);
for(int i
=1; i
<N
; i
++)
{
ans
= (len
[i
]+len
[i
-1])/2;
len
[i
] = ans
;
}
printf("%d", ans
);
return 0;
}
