数学建模社区-数学中国
标题:
求大牛给个高效算法
[打印本页]
作者:
气态水
时间:
2011-12-28 21:11
标题:
求大牛给个高效算法
boj 11841
' i) w& y" R2 O8 y" s) y# H% W
北邮开崛史
7 O1 O- D0 ]2 w4 l- J
Star it!
- O5 h2 K9 `) {& h A
6 G& w: |0 p) x+ V2 \1 O
Submit: 196 Accepted:33
9 C" Y9 P: d) g& y/ L, I7 n
Time Limit: 5000MS Memory Limit: 65536K
4 I- Z& R: E. i# i5 u; }
Description
9 m+ @/ Z$ ~" w) @
北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度，不仅在国内有着响亮的名号，在国际上也成了各国学子梦寐以求的学习圣地，为了更好地满足教学要求，学校决定在火星上建立分校区（当然那个时候地球早住不下那么多人了，没办法啊，只要跑到火星上去了），同时为了纪念200周年的校庆，学校决定为北邮的历代校长建立纪念碑（当然包括我们的林校长），但是土地上坑坑洼洼的（没办法啊，火星毕竟是火星），堪查队事先把地表的情况都堪测好了，他们把地表数据用海拔高度表示，保存在了一个数组A之中，现在要求找出一块最长的空地，但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值，这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队，这样大的计算量早就超出了他们的能力范围，好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在，你做为热心的火星人，用你高超的计算能力去解决这一问题吧。
z" E! ~; @8 }0 @3 _( [
' ], j0 h' U9 C+ C7 |. x. A3 \/ D
Input
& ~/ X3 ]2 Z4 |, {1 w
第一行为两个整数N和M，N.为记录地表数据数组中数据的总数，M为要求的高度差。
9 D. H Y3 @+ u
第二行为地表数据数组A，有N个整数，每两个整数之间用空格隔开，其中A[i] < 100000000;
* V; @& K1 L" `) N; O9 K: J
1 < N <= 1000000;
. D* s" f% Q9 n# D' N6 u) o
M < 1000000;
/ Z/ X, j4 P% @5 F
. ?5 D" W/ P( f7 D
! B! I8 N7 ^3 G
Output
: V% @; Y3 ]5 N( z" y0 [
一个整数LEN，表示在地表数据数组中，求最长的连续的一段，并且该段里面的最大值和最小值之差不大于M。
( B# e. h) k- i. Z* B+ n. E
LEN为那段的长度。
- u% O& \$ C* W" }+ @- x8 o
1 z* c8 `: [+ P4 [
0 c% Q% O m8 \
Sample Input
# k- a3 g& r6 P- f
# t5 D" ^& k) [ r
10 5
& r2 _& ?3 G$ C6 d* Z
1 5 7 3 5 2 2 2 1 7
" H8 g1 K9 Y/ p/ C1 N. ^& U7 b
' T8 C1 `: j8 M$ J0 A( m+ ?; R
3 [0 W9 P7 b1 }) H& F: [# ^4 C( K
Sample Output
5 v+ k: X1 ]" p, {9 Y
- ^" d+ ^ ]6 X6 ~4 T
7
& r2 Y) v7 q# C2 j2 x/ u
. A. ]5 I8 M8 p& R, x9 g
, C4 Z8 G( O5 ^9 t
Hint
, H; r1 J0 o$ ?; b
SAMPLE中，从2到8这段中，最大值为7，最小值为2，他们之间的差为5，且他们是最长的一段。
; p4 M9 V6 ~6 j/ W2 ?
' F+ O$ i2 _4 [2 P. H& T6 Y
我用暴力，结果超时了
3 J( T* Z0 _5 b5 x4 m3 T
请大牛个个算法
; ^4 Q; l. y, R- \, T( D* t: N# C
最好附上核心代码~~
, E1 Y& N( n5 q% [& e
谢谢
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5