备考华杯赛：考前练习一
&&&&标签：
郑州奥数网12月13日
第十八届华杯赛即将开始接受网上报名，奥数网整理了一些考前练习，有意愿的考生可以先进行练习备考（第十八届华杯赛每周一练试题及解析汇总）。
题目：在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时通过。如果各自单独过桥的话，四人所需要的时间分别是1，2，5，8分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，你如何设计一个方案，让用的时间最少。
（1）1分钟的和2分钟的先过桥（此时耗时2分钟）。
（2）1分钟的回来（或是2分钟的回来，最终效果一样，不赘述，此时共耗时3分钟）。
（3） 5分钟的和8分钟的过桥（共耗时2？1？8？11分钟）。
（4）2分钟的回来（共耗时2？1？8？2？13分钟）。
（5）1分钟的和2分钟的过桥（共耗时2？1？8？2？2？15分钟）。
此时全部过桥，共耗时15分钟。
杯赛竞赛类别NYOJ 47过河问题
主要思路:先排序。有两种可能是最小的情况，一种是让最小的去带着最大的过去，然后最小的再回来，还有一种就是先最小的和第二小的一块过去， 然后最小的回来，让最大的和第二大的过去，接着第二小的回来，第二小和最小的接着在过去，最小的接着回来，主要就是这两种，用的时候判断一下，接着的问题就是n是奇数还是偶数的问题
排完序之后的a[0]最小, a[n-1]最大，第一种的时间为a[0] + a[n -1] + a[0] + a[n - 2];其中a[0]是最短的时间，a[n-1]是最大的时间，下面一样， 第二种的时间为a[n -1] + a[1] + a[1] + a[0];其中a[1]是第二小的时间。最后要判断是奇偶数，具体代码如下，代码上有注释:
1 #include &stdio.h&
2 #include &stdlib.h&
4 int main()
int t, i, j, tmp, sum,
scanf("%d", &t);
while(t --)
int n, a[1001];
scanf("%d", &n);
for(i = 0; i & i ++)
scanf("%d", &a[i]);
for(i = 0; i & n - 1; i ++)//选择排序
for(j = i + 1; j & j ++)
if(a[index] & a[j])
tmp = a[index];
a[index] = a[i];
if(n &= 2)//如果n为1或者为2 的时候，只需要进行一次过桥，时间为最后一个人的
printf("%d\n", a[n - 1]);
sum = a[1];
while(n & 3)//当n & 3的时候过桥时间有个规律，最短一共两种，一种是最短时间的那个人带着最长的那个过，然后自己再回来，还有就是先最长的两个过去，第二短的回来，第一第二短在过去，第一短再回来
if(a[0] + a[n - 1] + a[0] + a[n - 2] & a[n - 1] + a[1] + a[1] + a[0])//这里判断当用最小的运过去与普通方法运过去的大小
sum += a[n - 1] + a[1] + a[1] + a[0];
sum += a[0] + a[n - 1] + a[0] + a[n - 2];
n -= 2;//将n减少2,因为一次过去两个
if(n == 3)//这里判断有两个用途，一个实判断是否是奇数，就是最后还剩三个，还有就是刚开始是奇数的时候
sum += a[2] + a[0];
printf("%d\n", sum);
> 本站内容系网友提交或本网编辑转载，其目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请及时与本网联系，我们将在第一时间删除内容！
链接:NYOJ:click here POJ:click here 题意: 在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边.如果不借助手电筒的话,大家是无论如何也不敢过桥去的.不幸的是,N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过.如果各自单独过桥的话,N人所需要的时间已知:而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时 ...
过河问题 时间限制:1 ms
内存限制:65535 KB 难度:5
描述 在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边.如果不借助手电筒的话,大家是无论如何也不敢过桥去的.不幸的是,N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过.如果各自单独过桥的话,N人所需要的时间已知:而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单 ...
时间限制:1000 ms
内存限制:65535 KB 难度:5 描述 在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边.如果不借助手电筒的话,大家是无论如何也不敢过桥去的.不幸的是,N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过.如果各自单独过桥的话,N人所需要的时间已知:而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动 ...
poj: http://poj.org/problem?id=1700 最简单的农夫过桥问题,贪心. 网上找的思路: /drizzlecrj/archive//931011.html 以下是构造N个人(N &= 1)过桥最佳方案的方法 1)如果N=1或者N=2,所有人直接过桥. 2)如果N ...
过河问题 时间限制:1000 ms
内存限制:65535 KB 难度:5 描述 在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边.如果不借助手电筒的话,大家是无论如何也不敢过桥去的.不幸的是,N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过.如果各自单独过桥的话,N人所需要的时间已知:而如果两人同时过桥,所需要的时间就是走得比较慢的那个 ...
前面做了几道比较简单的题目:下面我们来看这么一道题:NYOJ 0047 过河问题 时间限制:1000 ms
内存限制:65535 KB 难度:5 描述 在漆黑的夜里,N位旅行者来到了一座狭窄而且没有护栏的桥边.如果不借助手电筒的话,大家是无论如何也不敢过桥去的.不幸的是,N个人一共只带了一只手电筒,而桥窄得只够让两个人同时过.如果各自单独 ...
题意: 天黑后,N个人要过河,只有一个蜡烛且只有一条船,船每次最多坐2个人.不管怎样,过河者(1个人或者2个人)都必须有蜡烛,所以过河后可能需要人返回送蜡烛,然后再继续过河.问怎样过河时间最短. 思路: 贪心思想(一般都是先排序) 关键步骤:每次从此岸到彼岸移动的两个人要么这两个人中有一个是最快的那个人,要么这两个人到达彼岸后再也不回来.即:要么最快+最慢, ...
经典的贪婪. 两种方案:一个:让我们来最快,第二快,在过去的第一,最快的回.然后最慢,最慢第二,在过去.次最快的回来a[0]+a[1]+a[1]+a[n-1] 二:最快的和最慢的过去,最快的回来,最快的和当前最慢的过去,最快的回来.a[0]+a[n-1]+a[0]+a[n-2] 每次取最优解. 注意:最后剩余没过的人小于等于3的时候.要特殊推断. 代码: # ...您现在的位置：&&&&&&奥数题库
知识模块：
一道难倒公务员的趣味数学逻辑推理题
简介：在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，四...
5829 次浏览213 次下载
试题不错，送一朵花吧：
要评论？请先
，您也可以快捷登录：在漆黑的夜里,四位旅行者来到了一座狭窄而且没有护栏的桥边.如果不借助手电筒的话,大家是无论如何也不敢过桥去的.不幸的是,四个人一共只带了一只手电筒,而桥窄得只够让两个人同时过.如果各自单独过桥的话,四人所需要的时间分别是1、2、5、8分钟；而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间.如何设计一个方案,让这四人尽快过桥.
唯爱一萌878457
先1和2一起过,需要2分钟,然后1回来,共花3分钟5和8过,共花11分钟2回来,共花13分钟1和2过,共花15分钟第二步和第四步可以互换,总共花的时间一样,最短15分钟搞定
为您推荐：
其他类似问题
上面的不对，就一手电筒啊，让8和一先过，再让1和5过，然后2和5过
17分钟吧，先1和2过去，然后1回来分别带5和8过去
5和8一起，1和2一起，共用10分钟
楼上那位，后面没手电筒过不去，
1、按照题目所述：每两人一组，过桥的时间均为8分钟。2、任意两人组合过桥，都需要过桥3次，共花费8X3=24分钟。3、因此，要缩短过桥时间，只有缩短回程所需的时间。4、每人编号：A(1分钟)，B(2分钟)，C(5分钟)，D(8分钟)。5、显然，单人过桥，A的时间最短，也就是说，A返程所花时间最短。6、组合：AB（往8分钟）--A（返1分钟）--AC...
扫描下载二维码POJ-1700 &&NYOJ 47 过河问题【贪心】-爱编程
POJ-1700 &&NYOJ 47 过河问题【贪心】
链接：NYOJ:click here POJ:click here
在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。
贪心思想（一般都是先排序）
每次从此岸到对岸移动的两个人要么这两个人中有一个是时间最快的那个人，要么这两个人到达对岸后再也不回来。即：要么最快+最慢（最快回来换人），要么最慢+次慢（不回来）。
1.对N个人过河时间从小到大排序。cost[i];
2.分情况讨论：
⑴当n = 1，直接过河。sum = cost[0]
(2)当n = 2，直接过河。 sum = cost[1]
(3)当n = 3，无论怎么过河， sum = cost[0] + cost[1] + cost[2]&
(4)当n = 4，设从小到大排序后位a=cost[0],b=cost[1],c=cost[2],d=cost[3];
用最小的来送：b + a + c + a + d =2*a+b+c+d= 2*cost[0] + cost[1] + cost[2] + cost[3]（a,b过去，a回来，a,c过去，a回来，a,d过去）
两小送两大：b + a + d + b + b =a+3*b+d= cost[0] + 3*cost[1] + cost[3](a,b过去，a回来，c,d过去，b回来，a,b过去）
所以sum = min(2a + b + c + d, a + 3b + d)
(5)当n & 4，设从小到大排序后位a,b,……,c,d，大于4个人，a,b是最小的两个人，c,d是最大的两个人，目标就是把最大的两个人送过去。就要牺牲最小的。
用最小的来送：A=d + a + c + a = 2a + c + d=2*cost[0]+cost[2]+cost[3](a,d过去，a回来，a,c过去，a回来）
两小送两大：B= b + a + d + b = a + 2b + d=cost[0]+2*cost[1]+cost[3];(a,b过去，a回来，c,d过去，b回来）
循环：sum = min(A,B)，直到n &= 4时候结束。
思路理解清晰，代码不难实现：
//NYOJ 47 过河问题：
//POJ 1007
#include &stdio.h&
#include &string.h&
#include &iostream&
#include &algorithm&
int cost[1010];
int main()
//freopen(&1.txt&,&r&,stdin);
//freopen(&2.txt&,&w&,stdout);
int ncase,m,n,i,j;
scanf(&%d&,&ncase);
while(ncase--)
scanf(&%d&,&m);
memset(cost,0,sizeof(cost));
for(i=0; i&m; i++)
scanf(&%d&,&cost[i]);
sort(cost,cost+m);
sum+=cost[0];
else if(m==2)
sum+=cost[1];
else if(m==3)
sum+=(cost[0]+cost[1]+cost[2]);
else if(m==4)
sum +=min(2*cost[0]+cost[1]+cost[2]+cost[3],cost[0]+3*cost[1]+cost[3]);
//if(cost[m-2]-2*cost[1]+cost[0]&=0)
//sum+=min(cost[m-1]+cost[m-2]+2*cost[0],)
sum+=min(cost[m-1]+cost[m-2]+2*cost[0],cost[m-1]+2*cost[1]+cost[0]);
printf(&%d\n&,sum);
版权所有 爱编程 (C) Copyright 2012. . All Rights Reserved.
闽ICP备号-3
微信扫一扫关注爱编程，每天为您推送一篇经典技术文章。}