请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1572|回复: 0

求大牛给个高效算法

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

1

主题

4

听众

6

积分

升级  1.05%

该用户从未签到

发表于 2011-12-28 21:11 |显示全部楼层
|招呼Ta 关注Ta
boj 11841% T7 P4 n7 x6 U2 h$ P) g3 A& g
北邮开崛史
: P8 P, l+ z" `Star it!   # v( a; B) k" b& _) h. f! `1 x- b7 v

& k5 j1 @: w' m* Q. C- RSubmit: 196 Accepted:33
. q; @+ k! C- n7 r/ \* r- Q1 WTime Limit: 5000MS Memory Limit: 65536K* C5 l3 X6 l+ o4 e2 U: G
Description
0 _$ ~5 N" W  C- t0 b北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度,不仅在国内有着响亮的名号,在国际上也成了各国学子梦寐以求的学习圣地,为了更好地满足教学要求,学校决定在火星上建立分校区(当然那个时候地球早住不下那么多人了,没办法啊,只要跑到火星上去了),同时为了纪念200周年的校庆,学校决定为北邮的历代校长建立纪念碑(当然包括我们的林校长),但是土地上坑坑洼洼的(没办法啊,火星毕竟是火星),堪查队事先把地表的情况都堪测好了,他们把地表数据用海拔高度表示,保存在了一个数组A之中,现在要求找出一块最长的空地,但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值,这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队,这样大的计算量早就超出了他们的能力范围,好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在,你做为热心的火星人,用你高超的计算能力去解决这一问题吧。: c1 D- ^- g* o. h/ j
6 i7 r- m' _: U- x4 D: w7 |; [
Input
) F9 b  ]8 H% z第一行为两个整数N和M,N.为记录地表数据数组中数据的总数,M为要求的高度差。
1 k" S4 d) K8 C$ J1 k# c+ [4 \; f第二行为地表数据数组A,有N个整数,每两个整数之间用空格隔开,其中A[i] < 100000000;+ U, O! V; g* G2 a: p
1 < N <= 1000000;
! P5 F0 q7 s; i  ]M < 1000000;: N. r6 _2 Y" D% F

, O( L/ _  F- \5 A! l% G$ T" G4 ^" O9 R8 N0 W
Output
  p8 A9 w: Q- V8 _! {* T一个整数LEN,表示在地表数据数组中,求最长的连续的一段,并且该段里面的最大值和最小值之差不大于M。
( i2 P4 \5 f2 f5 y) z% _LEN为那段的长度。
: I( b% X  A' }# v/ x7 A" l* r8 j$ v# T
! J$ B- b$ B; b( o
Sample Input
8 @* v# J8 j. \3 k) I0 m8 F2 _2 C, n
10 5
& R6 y! y' U/ P! F1 5 7 3 5 2 2 2 1 7
5 r' g  m* _/ j/ }0 i5 f& w5 v5 L: r9 A$ Z; I

6 D1 V9 F9 i8 p1 j( f* |3 ?8 ^! JSample Output! a& m: c' H- S* ?8 [  u5 b
: e2 a& D8 N7 x, q+ `! j
7* m% x9 e: u- y6 r/ b! I/ L) |# i

1 Y; W% f" b' D1 r* A( X0 r" g: Q/ \% X7 m
Hint
6 w+ a5 l9 U2 P% c. i9 d5 `SAMPLE中,从2到8这段中,最大值为7,最小值为2,他们之间的差为5,且他们是最长的一段。( i7 ^+ I+ f, o  Q. m5 y* m

8 G6 C; O' ?4 X我用暴力,结果超时了
  ^. d7 o+ m" J* ~请大牛个个算法" j# w$ E8 h1 a& y
最好附上核心代码~~
: f) ~' |0 K$ S, e! Y# ]" k4 b谢谢
zan
您需要登录后才可以回帖 登录 | 注册地址

qq
收缩
  • 电话咨询

  • 04714969085
fastpost

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

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

蒙公网安备 15010502000194号

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

GMT+8, 2024-3-29 14:12 , Processed in 0.418642 second(s), 51 queries .

回顶部