QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2296|回复: 0
打印 上一主题 下一主题

求大牛给个高效算法

[复制链接]
字体大小: 正常 放大
气态水        

1

主题

4

听众

6

积分

升级  1.05%

该用户从未签到

跳转到指定楼层
1#
发表于 2011-12-28 21:11 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
boj 11841
, x, O- l, N' o4 l1 P) b6 s北邮开崛史% E. _# r1 X; I& g3 P) ~
Star it!   
3 c- \5 X8 J& a0 l8 V6 ]) Q) u6 E5 b: O+ M+ L4 R
Submit: 196 Accepted:33( y3 r9 g4 N) A9 t/ Z3 w: O
Time Limit: 5000MS Memory Limit: 65536K& ?6 _) L7 H  b9 q% S
Description* t+ f( Z& d: r% n
北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度,不仅在国内有着响亮的名号,在国际上也成了各国学子梦寐以求的学习圣地,为了更好地满足教学要求,学校决定在火星上建立分校区(当然那个时候地球早住不下那么多人了,没办法啊,只要跑到火星上去了),同时为了纪念200周年的校庆,学校决定为北邮的历代校长建立纪念碑(当然包括我们的林校长),但是土地上坑坑洼洼的(没办法啊,火星毕竟是火星),堪查队事先把地表的情况都堪测好了,他们把地表数据用海拔高度表示,保存在了一个数组A之中,现在要求找出一块最长的空地,但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值,这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队,这样大的计算量早就超出了他们的能力范围,好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在,你做为热心的火星人,用你高超的计算能力去解决这一问题吧。
1 B$ H& f" @7 v/ v* y
/ `4 ]" \8 ^0 iInput2 u4 l7 D9 o& j' I# n; o
第一行为两个整数N和M,N.为记录地表数据数组中数据的总数,M为要求的高度差。* s) W7 d! [) J2 K5 K
第二行为地表数据数组A,有N个整数,每两个整数之间用空格隔开,其中A[i] < 100000000;& y( z5 p) D9 w# ?
1 < N <= 1000000;- K5 j- e: e0 j( Y3 u
M < 1000000;
2 }' n' V8 U% z+ K
' I" \2 p% {5 S3 m- G- D/ ~  p- n4 m( R7 d, m: Z& Z. G1 M6 _( O
Output9 R5 R' r, f, C" O' Y  _, T
一个整数LEN,表示在地表数据数组中,求最长的连续的一段,并且该段里面的最大值和最小值之差不大于M。
$ {0 M" o8 V0 N# yLEN为那段的长度。
- z; k6 e. a1 D3 p
0 {- w/ a2 q! f2 Q! ?' V  x% D9 o) m* b4 @, k/ v3 C& @2 k
Sample Input
' y9 {  }9 I! `. P: ~) r+ M6 g- v! y5 M- K& ]$ j, i- Y5 a9 H
10 5
: [. T2 R% p* R& M) y: X1 5 7 3 5 2 2 2 1 7
+ N/ F' I& s& k" d# g+ Q/ q. {( f
  E' [4 Q8 ^/ {3 Q5 ?* g5 A: z; R( D3 {6 h% {
Sample Output' p, }! l% _  Z# A, {" |1 p9 M
% @& U5 Q9 {8 n( Y
7
& [2 E5 T" X5 X( e7 ~& w* X& ?5 d, y8 f/ d! E1 W
# q* H3 f3 U. U3 s* o+ M
Hint
) Q& ?% P' M' m5 H, s9 m+ P- T5 aSAMPLE中,从2到8这段中,最大值为7,最小值为2,他们之间的差为5,且他们是最长的一段。
8 B- M$ [, [# r) {; x2 a8 ?
2 c( p/ P* P5 K$ G, B我用暴力,结果超时了5 U% J% T) o& R; W) F2 h/ T" O3 b
请大牛个个算法
3 ^8 S) n8 @2 S: i, g最好附上核心代码~~, T7 O9 I3 O! v- D$ p3 }& O
谢谢
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

手机版|Archiver| |繁體中文 手机客户端  

蒙公网安备 15010502000194号

Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

GMT+8, 2025-7-24 00:57 , Processed in 0.345619 second(s), 50 queries .

回顶部