QQ登录

只需要一步,快速开始

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

求大牛给个高效算法

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

1

主题

4

听众

6

积分

升级  1.05%

该用户从未签到

跳转到指定楼层
1#
发表于 2011-12-28 21:11 |只看该作者 |正序浏览
|招呼Ta 关注Ta
boj 11841
" g; e4 x8 {9 {. d( \北邮开崛史  |& \" m7 h( c- h1 k' O9 s
Star it!   
7 v- k/ N( c  v
7 I! Q3 h# D; s4 o- ?0 rSubmit: 196 Accepted:33
: J3 i4 t. C' j) [' p# rTime Limit: 5000MS Memory Limit: 65536K
7 [  {0 F3 l' oDescription8 X: r5 _6 i- U
北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度,不仅在国内有着响亮的名号,在国际上也成了各国学子梦寐以求的学习圣地,为了更好地满足教学要求,学校决定在火星上建立分校区(当然那个时候地球早住不下那么多人了,没办法啊,只要跑到火星上去了),同时为了纪念200周年的校庆,学校决定为北邮的历代校长建立纪念碑(当然包括我们的林校长),但是土地上坑坑洼洼的(没办法啊,火星毕竟是火星),堪查队事先把地表的情况都堪测好了,他们把地表数据用海拔高度表示,保存在了一个数组A之中,现在要求找出一块最长的空地,但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值,这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队,这样大的计算量早就超出了他们的能力范围,好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在,你做为热心的火星人,用你高超的计算能力去解决这一问题吧。7 W  n7 t& ?4 e

+ ]$ t8 r. q; N0 d3 t2 x/ oInput
9 F1 F+ Y- K  c+ k$ K" [2 _4 b- l8 Q第一行为两个整数N和M,N.为记录地表数据数组中数据的总数,M为要求的高度差。- ?% M% Q- c  x) w8 |
第二行为地表数据数组A,有N个整数,每两个整数之间用空格隔开,其中A[i] < 100000000;
; X9 Q0 ]) G2 C- p7 D1 < N <= 1000000;! d. C8 D& q& g: N
M < 1000000;0 P8 {0 x5 x& s' I: T7 r

6 O' C8 A; q& N4 y1 f) r* x4 ?0 _" y1 a0 v! P! r% L- k9 v9 N/ d
Output
5 G" J2 Z! _+ n' z3 Z8 q一个整数LEN,表示在地表数据数组中,求最长的连续的一段,并且该段里面的最大值和最小值之差不大于M。
; }' M  u/ I0 q" ?5 P$ F0 z( FLEN为那段的长度。
. b' Z+ c0 _# [4 z; Q1 x) H5 z
& H9 `4 }2 C! M& C4 }/ H/ \( g' ^. G/ O4 Z/ N/ D
Sample Input
4 g0 c% r$ s4 Z1 Q" q/ U! i2 B/ T+ p) D3 D4 c) ]
10 5. k* p* `' W3 H# m% o$ c, D* y
1 5 7 3 5 2 2 2 1 75 W; H+ [9 o, f' H3 I) R: H7 j
; ^# Z+ P0 M" d# Y9 @  z3 H
+ J. S4 g! x% Y1 X5 _5 O
Sample Output1 D+ _$ b. k# k9 g1 t- S: q2 i7 P
* m4 J8 I4 A0 b2 E* k2 a" a' |
7' X- Z* [1 B$ N, f+ ~& G, B. m$ |2 _& K
" _  a8 z: ~' X4 m# f% }& n7 P
! ?! [8 C& c7 Y' n
Hint
4 @. t" p& d! Z- F% c5 f4 mSAMPLE中,从2到8这段中,最大值为7,最小值为2,他们之间的差为5,且他们是最长的一段。: P& j/ l* r  B2 ]6 ]
, b! Q/ s: n' {' a
我用暴力,结果超时了% I( K  S* @0 B& j( v
请大牛个个算法
3 ]( z9 \) h1 N' j) M最好附上核心代码~~% d% W1 ^5 d/ \2 }; b1 ?5 Z, n
谢谢
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, 2026-8-6 08:17 , Processed in 0.903389 second(s), 52 queries .

回顶部