QQ登录

只需要一步,快速开始

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

求大牛给个高效算法

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

1

主题

4

听众

6

积分

升级  1.05%

该用户从未签到

跳转到指定楼层
1#
发表于 2011-12-28 21:11 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
boj 11841  }( }1 t4 p* D/ s) X  d7 }  r( ]
北邮开崛史+ X8 E) ~. g+ Q( Z4 ~! y
Star it!   5 R( m0 c8 k7 z- T/ J
) T) T+ x" {  K/ v7 B+ c: \
Submit: 196 Accepted:333 w# x/ @- u% P) h) n% {
Time Limit: 5000MS Memory Limit: 65536K) b6 h. s* G) T- Z% Y$ X
Description
+ u; q+ Q% X. q% I' H4 `0 y' \9 Z北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度,不仅在国内有着响亮的名号,在国际上也成了各国学子梦寐以求的学习圣地,为了更好地满足教学要求,学校决定在火星上建立分校区(当然那个时候地球早住不下那么多人了,没办法啊,只要跑到火星上去了),同时为了纪念200周年的校庆,学校决定为北邮的历代校长建立纪念碑(当然包括我们的林校长),但是土地上坑坑洼洼的(没办法啊,火星毕竟是火星),堪查队事先把地表的情况都堪测好了,他们把地表数据用海拔高度表示,保存在了一个数组A之中,现在要求找出一块最长的空地,但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值,这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队,这样大的计算量早就超出了他们的能力范围,好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在,你做为热心的火星人,用你高超的计算能力去解决这一问题吧。
5 `5 a7 p' X0 O! c& e7 }- _
% }8 ]. d4 m" R1 r( l* i, N. \Input
- `# Y$ z$ z) G第一行为两个整数N和M,N.为记录地表数据数组中数据的总数,M为要求的高度差。, A6 j; \0 X0 p# a* x
第二行为地表数据数组A,有N个整数,每两个整数之间用空格隔开,其中A[i] < 100000000;3 E8 m" s; }/ C! U' }/ @
1 < N <= 1000000;
- p! h' O+ l2 }M < 1000000;( f- {) a' g/ C+ V# `

& E) n  X- R9 ~) I% c- R
6 w4 L5 H5 |1 Z% n. iOutput
* D0 p  M# c1 s7 C4 b一个整数LEN,表示在地表数据数组中,求最长的连续的一段,并且该段里面的最大值和最小值之差不大于M。* @: Y' J" m: u: d
LEN为那段的长度。
8 O) `6 [" j, I0 X- j" n6 K5 b% ?" [/ c( Q. j

/ v4 s% D1 n3 f, `( z3 K5 MSample Input
- s- o! o: H* b: v) ^  O& e3 l; \: [# r
10 5, ^7 r7 r/ A: P+ ]9 z" h
1 5 7 3 5 2 2 2 1 7
8 a# p; u: S$ |( c' v, V
" b5 M4 y8 K/ B6 m% u9 f/ M# \' z) {8 z- \" C$ W  X& [/ S4 |" o9 X
Sample Output
4 Y2 q) `4 B% U6 L' d* N2 ^
1 \9 k: x3 \& e' Q' k7 T7
, ^9 ~" E8 u- A, e- W- G3 d/ r- e
+ [. k- w2 E. d: X. k9 n2 w/ d
2 b4 X2 ?7 W$ c& N' Y7 IHint# V8 ~& N7 O! u& |# v' A. W
SAMPLE中,从2到8这段中,最大值为7,最小值为2,他们之间的差为5,且他们是最长的一段。0 P9 G9 _4 v) ?$ B. }" X4 F
: [; x6 b) S- A% E9 r
我用暴力,结果超时了
5 O$ G% Z. i7 C+ v1 K+ A: w, G: g请大牛个个算法# U7 Q* h; M' G
最好附上核心代码~~
) G+ j7 V4 \2 |9 l8 {: V谢谢
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-8-1 05:37 , Processed in 0.411733 second(s), 51 queries .

回顶部