NYOJ 47-过河问题

时间限制:1000 ms | 内存限制:65535 KB | 难度:5

描述

在漆黑的夜里,$N$位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,$N$个人一共只带了一只手电筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,$N$人所需要的时间已知;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,如何设计一个方案,让这$N$人尽快过桥。

输入

第一行是一个整数 $T(1<=T<=20)$ 表示测试数据的组数
每组测试数据的第一行是一个整数 $N(1<=N<=1000)$ 表示共有 $N$ 个人要过河
每组测试数据的第二行是 $N$ 个整数 $Si$ ,表示此人过河所需要花时间。$(0<Si<=100)$

输出

输出所有人都过河需要用的最少时间

样例输入

1
4
1 2 5 10

样例输出

17

题目来源

http://acm.nyist.net/JudgeOnline/problem.php?pid=47

例子思路:1和2过去1回来,时间为2+1=3;5和10过去2回来,时间为3+10+2=15; 1和2再一起过去,时间为15+2=17。

问题思路

首先对输入的数组进行排序。sort(Si,Si+N)

当人数大于等于4的时候

  1. 一开始只用了例子里面的方法,$Si[0]$和$Si[1]$过去,$Si[0]$回来,$Si[1]$留在对岸;$Si[n-1]$和$Si[n-2]$过去,$Si[1]$回来,$Si[n-1]$,$Si[n-2]$留在对岸;这样过去了两个人,所用时间为$Si[1]+Si[0]+Si[n-1]+Si[1]$。
  2. 其实还有另一种情况:$Si[0]$和$Si[n-1]$过去,$Si[0]$回来,$Si[n-1]$留在对岸;$Si[0]$和$Si[n-2]$过去,$Si[0]$回来,$Si[n-2]$,$Si[n-1]$留在对面;所用时间为$Si[n-1]+Si[0]+Si[n-2]+Si[0]$。

当人数为3的时候

  • $Si[1]+Si[0]+Si[2]$

当人数为2的时候

  • $Si[1]$

当人数为1的时候

  • $Si[0]$

程序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
int T,N,i,sum=0;
int *Si;
cin>>T;
while(T--){
cin>>N;
Si = new int[N];
for(i = 0; i<N; i++){
cin>>Si[i];
}
sort(Si,Si+N);
while(N>=4){
if(Si[1]+Si[0]+Si[N-1]+Si[1] < Si[N-1]+Si[0]+Si[N-2]+Si[0])
sum = sum + Si[1]+Si[0]+Si[N-1]+Si[1];
else
sum = sum + Si[N-1]+Si[0]+Si[N-2]+Si[0];
N = N-2;
}
if(N == 3) sum = sum + Si[1]+Si[0]+Si[2];
if(N == 2) sum = sum + Si[1];
if(N == 1) sum = sum + Si[0];
cout<<sum<<endl;
sum = 0;
delete Si;
}
}
文章目录
  1. 1. 问题思路
  2. 2. 程序实现

20160315-acm-5/

本页二维码