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