[ACM_NYOJ_47]过河问题
杰拉斯 | 时间:2013-05-07, Tue | 27,154 views编程算法
过河问题
时间限制:1000 ms | 内存限制:65535 KB
描述
在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过。如果各自单独过桥的话,N人所需要的时间已知;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,如何设计一个方案,让这N人尽快过桥。
输入
第一行是一个整数T(1<=T<=20)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过河
每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0 输出所有人都过河需要用的最少时间 练了几天ACM,今天首次尝试难度系数为5的题,结果就被难住了,因为从样例输入怎么都想不到如何才能够让最短时间为17。甚至开始怀疑题目有问题,但觉得还是不太甘心,百度了一下,才发现是自己太想当然,其实如果能够拿纸笔画一画就知道是怎么回事了。 思路如下: 先将数组S按过河时间从小到大排好序。 代码如下: 如需转载请注明出处:杰拉斯的博客输出
样例输入
1
4
1 2 5 10
样例输出
17
来源
即简化为送最慢的两个人先过河,在这两种情况中取花费时间最少的方式,规模缩小为n - 2的同一问题
#include<stdio.h>
#include<algorithm>
using namespace std;
int s[100];
int main(){
int t, n;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", s + i);
}
sort(s, s + n);
int time = 0;
while(n > 3){
int time1 = s[1] + s[0] + s[n - 1] + s[1];
int time2 = s[n - 1] + s[0] + s[n - 2] + s[0];
time += time1 < time2 ? time1 : time2;
n -= 2;
}
if(n == 3){
time += s[0] + s[1] + s[2];
}else if(n == 2){
time += s[1];
}else if(n == 1){
time = s[0];
}
printf("%d\n", time);
}
return 0;
}
相关文章
超难的样子。。
@Comfish
理顺了就不难了。
看样子比赛是比算法.但是为什么#include呢?有iostream原生对象处理啊.
你是指stdio.h?
拿到这道题根本没想法,看了学长的博文,感觉好像好简单的样子,哎,还是太弱了。。。
好像并没有这么简单,我拿更多的数据测试了下,你的算法有问题。我用的递归算法解决的这个问题
能否给一个无法通过的测试用例呢?不过我工作后也好久没碰 ACM 了,哎~