数学建模社区-数学中国
标题:
求大牛给个高效算法
[打印本页]
作者:
气态水
时间:
2011-12-28 21:11
标题:
求大牛给个高效算法
boj 11841
! U' x' ]! ]! F& t, o( {# j
北邮开崛史
5 [9 \4 `% P7 I6 k0 ?7 [
Star it!
0 Q6 t. D, k) ~ _; m: A% P! M
+ t8 z5 e5 c$ n; }( l& m6 q
Submit: 196 Accepted:33
L" d2 f( t5 U. A* V
Time Limit: 5000MS Memory Limit: 65536K
! y' p F5 O! _8 E/ j. e
Description
# w* u2 a4 ?2 \+ I) T
北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度，不仅在国内有着响亮的名号，在国际上也成了各国学子梦寐以求的学习圣地，为了更好地满足教学要求，学校决定在火星上建立分校区（当然那个时候地球早住不下那么多人了，没办法啊，只要跑到火星上去了），同时为了纪念200周年的校庆，学校决定为北邮的历代校长建立纪念碑（当然包括我们的林校长），但是土地上坑坑洼洼的（没办法啊，火星毕竟是火星），堪查队事先把地表的情况都堪测好了，他们把地表数据用海拔高度表示，保存在了一个数组A之中，现在要求找出一块最长的空地，但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值，这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队，这样大的计算量早就超出了他们的能力范围，好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在，你做为热心的火星人，用你高超的计算能力去解决这一问题吧。
3 W- g- X" R4 D: D
T, q7 Q% W: o( Z5 A
Input
+ i+ z2 I% N' K* X$ o" c R+ R
第一行为两个整数N和M，N.为记录地表数据数组中数据的总数，M为要求的高度差。
% |+ Y* H/ n6 R0 o2 H7 c# H3 d, C7 n
第二行为地表数据数组A，有N个整数，每两个整数之间用空格隔开，其中A[i] < 100000000;
& ]0 C+ I2 | [* N# @
1 < N <= 1000000;
6 K- w4 M; S5 m/ c" y- `0 k/ p
M < 1000000;
' x( t5 V2 A$ y% k! O) P3 r# D
1 i6 T$ d3 B' y, Q
9 Z$ Z( |- V, m2 M* G o% G
Output
' f4 Z2 ]* N7 r: a3 e
一个整数LEN，表示在地表数据数组中，求最长的连续的一段，并且该段里面的最大值和最小值之差不大于M。
* ~ k& `9 ]; q# b
LEN为那段的长度。
$ i0 C3 v$ t# f
& R; o: n" I' E6 w6 c8 ^; f* P
8 C5 h" V5 k! n9 D
Sample Input
7 ]# n! f0 i: s6 p
2 d" d5 Y/ L) Z2 r0 F+ u7 f
10 5
, q# g" {+ ]+ n: X, Z
1 5 7 3 5 2 2 2 1 7
# c6 P0 u9 B% [: j# }2 {0 L
1 p2 k8 l1 A# F/ {3 i
: `) E- _' K- b* R, o7 A7 C4 \
Sample Output
" y/ x/ r9 z; E- L) O
6 U" a" {! P: I1 q* r+ y% O
7
8 ]+ H9 M6 G7 r
( B) @* z" [: o5 ?
% Q$ Z6 }6 T+ }% {0 R) X5 {5 x
Hint
, Q i# ~# c+ c% |1 j
SAMPLE中，从2到8这段中，最大值为7，最小值为2，他们之间的差为5，且他们是最长的一段。
( ]! j! g( r$ U6 X; S+ r( K+ i' w
U; P! {5 S& W. G+ e# I7 U
我用暴力，结果超时了
0 n' j6 k6 [, X3 [* U
请大牛个个算法
# ~% z& |2 n. F2 y- p; O
最好附上核心代码~~
4 T8 z6 B+ [) \' P
谢谢
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5