- 在线时间
- 1 小时
- 最后登录
- 2012-1-1
- 注册时间
- 2011-12-28
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 6
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 6
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级 1.05% 该用户从未签到
|
发表于 2011-12-28 21:11
|显示全部楼层
|
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
|