A27370. 过河问题
填空题
较易
知识点
题目描述
过河问题
题目描述
有 n 个人要渡河，但只有一条小船，这条小船一次只能坐下最多两个人，并且只有一副船桨。每个人划船的速度不一样，如果两个人一起上船，由于重量变大，划船的速度基本上相当于是划船速度最慢的那个人速度。假设给出每个人单独划船过河所花费的时间 Ti，请问所有人都过河的总时间最短的时间？
输入格式
输入两行，第一行是一个整数，表示要过河的 n 个人。
第二行，是 n 个整数，按速度从快到慢排序好的每个人划船过河的时间。
输出格式
输出一行，给出所有人过河所花费最短的时间。
样例输入 1
3
1 2 3样例输出 1
6样例输入 2
4
1 2 5 10样例输出 2
17注意事项
请严格按要求输出，不要多余的打印语句，例如：“输入 x=...” 等多余内容。
本程序的代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main 函数需要返回 0。
注意: 只使用 ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include<xxx>， 不能通过工程设置而省略常用头文件。
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int a[n+5];
for(int i=1; i<=n; i++) cin>>a[i];
sort(a+1,a+n+1);
int s=0;
while(n>=4) {
if(2*a[1]+a[n-1]+a[n]>2*a[2]+a[1]+a[n]) {
s+=2*a[2]+a[1]+a[n];
} else s+=2*a[1]+a[n-1]+a[n];
n-=2;
}
if(n==3) s+=a[1]+a[2]+a[3];
else if(n==2) s+=a[2];
else s+=a[1];
cout<<s<<endl;
return 0;
}
上一题
下一题