过桥问题 其实很水 就是很水
题目描述
在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2<=N<1000)和这N个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸.
例如,有3个人甲 乙 丙,他们单独过桥的时间分别为1 2 4,则总共最少需要的时间为7.具体方法是:甲 乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲,丙在一起过桥到河的左岸,总时间为2+1+4=7.
输入
第一行为T，表示有T组数据，每组数据有两行
第一行为N，表示有N个人
下面一行有n个数，表示每个人的过河时间
输出
全部人过河的最短时间
样例输入
2
3
1 2 4
4
1 2 5 10
样例输出
7
17
提示
#include
#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int i,a[1005];
int n;
cin>>n;
for(i=0;i
cin>>a[i];
}
sort(a,a+n);
int d=0,j=n-1;
if(n>2){
for(i=1;n>0;i++)
{
if(i%4==1)
{
d=d+a[1];
n=n-2;
}
if(i%4==2)
{
d=d+a[0];
n=n+1;
}
if(i%4==3)
{
d=d+a[j];
j=j-2;
n=n-2;
}
if(i%4==0)
{
d=d+a[1];
n=n+1;
}
}
cout<
else cout<
return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！