| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1584 人关注过本帖
标题:登山问题 --- NOI 92
只看楼主 加入收藏
Arcticanimal
Rank: 3Rank: 3
等 级:论坛游民
威 望:7
帖 子:341
专家分:20
注 册:2007-3-17
收藏
 问题点数:0 回复次数:13 
登山问题 --- NOI 92
Editted the title so that it is more descriptive.

To Original poster:

Please make the problem statement more precise.


在csdn里看到这个题目

《登山问题》
有一支登山队伍(k人)要去爬一座很高很高的山,每一个人上山和下山都需要N天。每个人出发时带一定的干福ǖ趇人带M[i]),每天会消耗一定量的干粮( 第i人每天消耗E[i] ).队员同时出发,要求出发N天后有人到达山顶,出发2N天后无人滞留山上。由于可能 M[i]<=E[i]* 2N 可以有队员中途折回,把干粮让给其他的同伴(保证自己要能活着回去!)

输入N
输入 k
输入 M[i]
输入 E[i]
输入保证有解的情况下
1。输出最省粮食的组队方法
2。输出人最少的组队方法

例如,输入 3 3
5 8 9
2 1 4
输出最省粮食的组队 第二个人 携带6的干粮 一个人上山
人最少的组队方法 第二个人 携带6的干粮 一个人上山

似乎有些麻烦,这样的题目除了穷举法有没有其他的算法呢?

[此贴子已经被HJin于2007-7-6 10:47:04编辑过]

搜索更多相关主题的帖子: 登山 NOI 
2007-07-04 20:19
天空の城
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2007-7-1
收藏
得分:0 
M[i]&lt;=E[i]* N 应该是 M[i]&lt;=E[i]* 2N 吧???

2007-07-04 20:48
天空の城
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2007-7-1
收藏
得分:0 

而且题目要求什么也没理解,我笨笨


2007-07-04 20:49
aipb2007
Rank: 8Rank: 8
来 自:CQU
等 级:贵宾
威 望:40
帖 子:2879
专家分:7
注 册:2007-3-18
收藏
得分:0 
似乎是个典型的算法,叫……算了,怕说错。

还没研究……
看看。

Fight  to win  or  die...
2007-07-04 20:49
Arcticanimal
Rank: 3Rank: 3
等 级:论坛游民
威 望:7
帖 子:341
专家分:20
注 册:2007-3-17
收藏
得分:0 
是 M[i]&lt;=E[i]* 2N ,打错了

try new catch
2007-07-04 21:02
dlcdavid
Rank: 3Rank: 3
来 自:成都
等 级:新手上路
威 望:6
帖 子:193
专家分:0
注 册:2005-12-23
收藏
得分:0 

1。输出最省粮食的组队方法
找出E[i]的值最低的第i个人,让他上山,就只需要E[i]*2N的粮食。
2。输出人最少的组队方法
人最少吗,就是一个人撒,,跟上面一样撒
或者就再判定是否每个i都有足够的粮食独自上山,然后,输出方法

不知道我是不是把题理解错了,,或者题可能有点问题


为了C++,我放弃了课本
为了高考,我又放弃了C++
现在而今眼目下,我能做什么?www.
2007-07-05 11:17
dlcdavid
Rank: 3Rank: 3
来 自:成都
等 级:新手上路
威 望:6
帖 子:193
专家分:0
注 册:2005-12-23
收藏
得分:0 
1。输出最省粮食的组队方法
应该还要求上去的人最多吧?

1.也就是说M[1]+M[2]+...+M[i]粮食总量M //应该是M[i]是第i+1个人的粮食携带量吧~~呵呵,,该是按你说的做
2.
M/(2N)就是每天的最大消耗量E,
3.再把E[i]排序
4.从低值加到高值,不超过E就行了撒.

2。输出人最少的组队方法
应该还要求尽量把粮食用完吧?

1.同上
2.同上
3.同上
4.逆序

为了C++,我放弃了课本
为了高考,我又放弃了C++
现在而今眼目下,我能做什么?www.
2007-07-05 11:33
HJin
Rank: 6Rank: 6
等 级:贵宾
威 望:27
帖 子:401
专家分:0
注 册:2007-6-9
收藏
得分:0 
It would be better that the author could give a few examples for each case and make the problem statement more precise.


I am working on a system which has no Chinese input. Please don\'t blame me for typing English.
2007-07-05 11:44
野比
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:24
帖 子:1627
专家分:516
注 册:2007-5-24
收藏
得分:0 

似乎队员可以在1-N的任一天上山... wow...


女侠,约吗?
2007-07-05 11:45
wsaaa
Rank: 1
等 级:新手上路
帖 子:136
专家分:0
注 册:2007-5-8
收藏
得分:0 

不怎么明白这个题目的意思啊!

2007-07-05 21:20
快速回复:登山问题 --- NOI 92
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025118 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved