在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。
#include<iostream>
#include<vector>
#include<algorithm>using namespace std;
int main(){vector
int T = 0;
cin >> T;
while(--T >= 0){
int n = 0, x = 0, temp = 0, method1 = 0, method2 = 0, ret = 0;
vector<int> left;
cin >> n;
while(++x <= n){
cin >> temp;
left.push_back(temp);
}
sort(left.begin(), left.end());
--x;
while(x > 3){
method1 = left[1] + left[0] + left[x - 1] + left[1];
method2 = left[x - 1] + left[0] + left[x - 2] + left[0];
ret += (method1 > method2? method2: method1);
x -= 2;
}
if(x == 3)
{
ret += left[2] + left[1] + left[0];
}
else if(x == 2)
{
ret += left[1];
}
else if(x == 1)
{
ret += left[0];
}
cout << ret << endl;
}
return 0;
}
全部评论
(0) 回帖