GitBook

这里写图片描述

分析可知(从小到大排序后) 过桥比较省时间的方法有两种

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]

#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;
}

题目地址:【NYOJ】[47]过河问题