博客

题目描述：几个人过河，每次过两人一人回，速度由慢者决定，问过河所需最短时间。

输入说明：输入t组数据，每组数据第1行输入n，第2行输入n个数，表示每个人过河的时间。

输出说明：输出t行数据，每行1个数，表示每组过河最少时间。

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n, sum = 0;
		cin >> n;
		vector<int> v(n, 0);
		for (int i = 0; i < n; i++)
			cin >> v[i];
		sort(v.begin(), v.end());
		int i;
		for (i = n - 1; i > 2; i -= 2)
		{
		// 法1： A + Z -> A
		//		 A + Y -> A
		//      Z + A + Y + A
		// 法2： A + B -> A
		//		 Y + Z -> B
		//       B + A + Z + B
		// 比较Y + A 和 2 * B
			if (v[i - 1] + v[0] > v[1] * 2)
				sum += v[1] * 2 + v[0] + v[i];
			else sum += v[i - 1] + v[0] * 2 + v[i];
		}
		if (i == 2)
			sum += v[2] + v[0] + v[1];// 0 + 2 -> 0   0 + 1
		else if (i == 1)
			sum += v[1];
		else sum += v[0];
		cout << sum << endl;
	}
	return 0;
}