| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 5840 人关注过本帖, 1 人收藏
标题:沙漠和绿洲
只看楼主 加入收藏
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
结帖率:99.34%
收藏(1)
已结贴  问题点数:100 回复次数:83 
沙漠和绿洲
这个是坛子里一位朋友贴的一个帖子 (联赛最难)地址如下:
https://bbs.bccn.net/thread-374948-1-1.html
为了大家方便看帖 具体的题目我还是黏贴过来 发个英雄帖求各位的解题思路
这个题目在建模方面比较有启发 自己处理的不好 向大家借鉴
杨大哥已经胸有成竹了 特别想看杨大哥的代码 呵呵。
程序代码:
在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。
为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此,只有与湖泊毗邻的第1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。
由于第N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。


【输入】

每行中两个数之间用一个空格隔开。
输入的第一行是两个正整数N 和M,表示矩形的规模。
接下来N 行,每行M 个正整数,依次代表每座城市的海拔高度。

【输出】

输出有两行。如果能满足要求,输出的第一行是整数1,第二行是一个整数,代表最少建造几个蓄水厂;如果不能满足要求,输出的第一行是整数0,第二行是一个整数,代表有几座干旱区中的城市不可能建有水利设施。

【输入样例】

2 5
9 1 5 4 3
8 7 6 1 2

【输出样例】

1
1
【样例说明】
只需要在海拔为9 的那座城市中建造蓄水厂,即可满足要求。


若是各位积极参与 我多给评分哦。
搜索更多相关主题的帖子: 沙漠 行政区划 
2012-08-17 09:30
zklhp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:china
等 级:贵宾
威 望:254
帖 子:11485
专家分:33241
注 册:2007-7-10
收藏
得分:11 
学习
收到的鲜花
  • 有容就大2012-08-17 10:33 送鲜花  10朵   附言:Z版贴个代码上来 再给10分 哈哈
2012-08-17 10:18
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
回复 2楼 zklhp
XX
OO


梅尚程荀
马谭杨奚







                                                       
2012-08-17 10:22
stophin
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:3
帖 子:227
专家分:618
注 册:2010-3-26
收藏
得分:11 
no picture no truth
但我是为分而来的
收到的鲜花
  • 有容就大2012-08-17 10:55 送鲜花  10朵   附言:分享下思路也成 呵呵
2012-08-17 10:51
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
回复 4楼 stophin
没图不影响吧。

梅尚程荀
马谭杨奚







                                                       
2012-08-17 10:52
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:11 
呵呵,我发现已经有人在网上开始搜答案了。没关系,只要能解答就好。
论坛里很久没见玩ACM水平高的人了,老杨很久没来了,小曹也消失一段时间了。
等大家三天,三天后如果还没有人成功我就要收分了
收到的鲜花
  • 有容就大2012-08-17 11:52 送鲜花  10朵   附言:恩 大家一起讨论 更好 杨大哥压轴

重剑无锋,大巧不工
2012-08-17 11:42
demonleer
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:10
帖 子:483
专家分:1225
注 册:2012-6-4
收藏
得分:11 
晚上回去试试,我先发,杨大哥压轴。。
收到的鲜花
  • 有容就大2012-08-17 11:53 送鲜花  10朵   附言:D版 也来了 呵呵 期待。
2012-08-17 11:45
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 7楼 demonleer
好的,等着各位一展英姿。
这个题目挺普遍的,很多学校的OJ上都有。送一个杭电的地址
http://acm.hdu.

重剑无锋,大巧不工
2012-08-17 11:48
stophin
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:3
帖 子:227
专家分:618
注 册:2010-3-26
收藏
得分:0 
额,弱弱的问一下,如果我有3行以上的话,只要保证最后一行全能到就行吗?中间如果有几个突兀的山峰不能到达也是输出1吗?
2012-08-17 12:13
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
回复 9楼 stophin
不管中间的吧 只要保证最后一行就行了。

梅尚程荀
马谭杨奚







                                                       
2012-08-17 13:08
快速回复:沙漠和绿洲
数据加载中...
 
   



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

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