数学建模社区-数学中国
标题:
求大牛给个高效算法
[打印本页]
作者:
气态水
时间:
2011-12-28 21:11
标题:
求大牛给个高效算法
boj 11841
+ f# y! e. b8 }* N
北邮开崛史
+ U4 g r! k8 }% @$ N% a `) X
Star it!
4 Q' A4 ~5 Y% q- k- o! v, \% e
, H9 W, f! M' V, t' c( o) j7 a
Submit: 196 Accepted:33
- p7 W; R9 `6 R& g) O. U
Time Limit: 5000MS Memory Limit: 65536K
R" f, [# ?1 V0 ^' _1 [0 T& J
Description
$ q, @3 ~# s1 X3 C" w
北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度，不仅在国内有着响亮的名号，在国际上也成了各国学子梦寐以求的学习圣地，为了更好地满足教学要求，学校决定在火星上建立分校区（当然那个时候地球早住不下那么多人了，没办法啊，只要跑到火星上去了），同时为了纪念200周年的校庆，学校决定为北邮的历代校长建立纪念碑（当然包括我们的林校长），但是土地上坑坑洼洼的（没办法啊，火星毕竟是火星），堪查队事先把地表的情况都堪测好了，他们把地表数据用海拔高度表示，保存在了一个数组A之中，现在要求找出一块最长的空地，但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值，这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队，这样大的计算量早就超出了他们的能力范围，好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在，你做为热心的火星人，用你高超的计算能力去解决这一问题吧。
5 e- C7 l' g# u7 q: E
! X# b$ O- S4 j; |( T
Input
$ \& J9 W4 T, U% p8 U% r
第一行为两个整数N和M，N.为记录地表数据数组中数据的总数，M为要求的高度差。
2 Q5 b3 T, ^9 M0 e
第二行为地表数据数组A，有N个整数，每两个整数之间用空格隔开，其中A[i] < 100000000;
5 M7 x! M1 B, W7 }; ]' p* ^6 `' R7 W
1 < N <= 1000000;
i1 P( g, `/ o8 z
M < 1000000;
9 ?2 T/ T; s! E
7 L, A% g4 v$ u2 L
$ m; C! n" A; e' y9 G" \. X# Z
Output
% H' \% Q( ?! H$ p& u$ }
一个整数LEN，表示在地表数据数组中，求最长的连续的一段，并且该段里面的最大值和最小值之差不大于M。
- a* C1 ~8 a+ {+ A
LEN为那段的长度。
5 v' v* {7 `$ m' _4 W: t' B. M
8 R; ~/ t0 p# o9 d
. p/ O# M0 O0 R& x5 W
Sample Input
$ W" {4 d( ]3 y( K5 Z# F
0 P$ r1 U% y( K# s/ b5 X" Z
10 5
9 ?/ o% q. o: ~4 l0 O
1 5 7 3 5 2 2 2 1 7
% _8 R @+ K8 Q2 z
! h7 w1 b( ^$ B @# n
, t( S2 g" [$ d
Sample Output
9 K x" x1 m, y) e: b
5 z0 U( x7 a0 ]" u! \% r
7
( \5 [% ], f6 I' v
* u, f& l) S, X- ^
1 n* }3 s; t# _! J- z- ~( g- T9 }
Hint
0 J* m: y( Y$ }; e* P
SAMPLE中，从2到8这段中，最大值为7，最小值为2，他们之间的差为5，且他们是最长的一段。
- J3 ^' C. T7 H( e7 R8 T0 L9 H9 b" R8 q- x
/ B- d, C3 L4 _3 ^8 o6 c
我用暴力，结果超时了
$ _, X8 o# d+ \$ ~1 z
请大牛个个算法
3 t* {9 j4 h2 Y* `5 T0 D; W
最好附上核心代码~~
& G& E4 u8 `7 E7 |5 ~8 [; x& D) H
谢谢
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5