问题描述
问题分析
分析可知(从小到大排序后)
过桥比较省时间的方法有两种
1、a[0] a[1]先过a[0]回
a[n] a[n-1]过 a[1]回
则总时间a[1]+a[0]+a[n]+a[1]
2、a[0]带a[n]过a[0]回
a[0]带a[n-1]过a[0]回
则总时间a[n]+a[0]+a[n-1]+a[0]
区别在与a[1]+a[1]与a[n-1]+a[0]
两者应该去更小的那一种方法
所以可以两两考虑
把最大的两个送过桥
当最后三人以下时
剩三人
则a[0]带a[2]过a[0]回
a[0]与a[1]过
总时间 a[2]+a[0]+a[1]
剩两人
a[0]与a[1]过
总时间a[1]
剩1人(说明总人数只有一人)
总时间a[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<stdio.h>
#include<algorithm>
using namespace std;
int a[1200];
int main() {
int T;
scanf("%d",&T);
while(T--) {
int n;
scanf("%d",&n);
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
sort(a,a+n);
int sum=0;
int i;
for(i=n-1; i>2; i-=2) {
sum+=min(a[1]+a[0]+a[i]+a[1],a[i]+a[0]+a[i-1]+a[0]);
}
if(i==2)
printf("%d\n",sum+a[0]+a[1]+a[2]);
else if(i==1)
printf("%d\n",sum+a[1]);
else
printf("%d\n",sum+a[0]);
}
return 0;
}
|