数学建模社区-数学中国
标题:
求大牛给个高效算法
[打印本页]
作者:
气态水
时间:
2011-12-28 21:11
标题:
求大牛给个高效算法
boj 11841
5 u" D- d7 i% i1 q7 ^7 Y
北邮开崛史
d6 E( z; \* l9 s% N) l
Star it!
( K: O0 ^ S7 B9 ]/ ]
Q5 T# K! g6 j: R
Submit: 196 Accepted:33
" E; b: f: X) r. w9 J- o- s4 ^
Time Limit: 5000MS Memory Limit: 65536K
6 ^) _4 a2 e) |
Description
2 d& ?6 U8 s' l4 {* M5 A
北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度，不仅在国内有着响亮的名号，在国际上也成了各国学子梦寐以求的学习圣地，为了更好地满足教学要求，学校决定在火星上建立分校区（当然那个时候地球早住不下那么多人了，没办法啊，只要跑到火星上去了），同时为了纪念200周年的校庆，学校决定为北邮的历代校长建立纪念碑（当然包括我们的林校长），但是土地上坑坑洼洼的（没办法啊，火星毕竟是火星），堪查队事先把地表的情况都堪测好了，他们把地表数据用海拔高度表示，保存在了一个数组A之中，现在要求找出一块最长的空地，但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值，这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队，这样大的计算量早就超出了他们的能力范围，好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在，你做为热心的火星人，用你高超的计算能力去解决这一问题吧。
! A' M7 Z$ W5 E# i
* m" v; S2 \1 u& f$ A7 Q. f+ D
Input
2 N( r3 `) g& H! N B" V
第一行为两个整数N和M，N.为记录地表数据数组中数据的总数，M为要求的高度差。
/ r( I" K# [" C; \6 W% `
第二行为地表数据数组A，有N个整数，每两个整数之间用空格隔开，其中A[i] < 100000000;
. i3 A" H6 A7 z- \
1 < N <= 1000000;
4 M# Y& o4 r! t# q8 g
M < 1000000;
! ?' O( g) F$ \% x0 `0 \/ d( P
7 p% f/ U7 c( p: k: P6 Y6 S
& u# U7 D* |* L- G! V
Output
9 l% v \: J5 o; _. u2 D3 i
一个整数LEN，表示在地表数据数组中，求最长的连续的一段，并且该段里面的最大值和最小值之差不大于M。
* X6 L0 W$ S0 q: T" g! I7 [
LEN为那段的长度。
7 F3 a% |& n( i( V- B# o9 ~: p4 C
' k3 Q/ W+ Z4 c4 k6 {% A% n3 q; T
" X* @& M2 T O. I
Sample Input
* a. F. O4 Y/ e5 h* N2 c& ~
* k' f ` M1 g4 @
10 5
" V3 y! |) I' W) X& ?
1 5 7 3 5 2 2 2 1 7
4 n2 @: c+ w- v6 M
5 X$ J$ W+ T; a5 U/ e+ p. i
- F+ s4 s6 E4 T7 L# i
Sample Output
, c' r! C1 p: m+ D- N+ `4 ?
8 W9 I* w, J o2 K/ L
7
8 D: x9 @* b8 C' q: T3 _- o
8 q$ v( t$ @' }
, J+ q) O9 {+ G
Hint
( L3 ]9 q2 ?; S
SAMPLE中，从2到8这段中，最大值为7，最小值为2，他们之间的差为5，且他们是最长的一段。
# Q4 b) f; V) `) v% @
% _) A7 f0 T% L& `3 s
我用暴力，结果超时了
! \! H A. o( ?2 [
请大牛个个算法
3 T4 n# ?9 z1 L! ^
最好附上核心代码~~
$ r8 U6 S: D {' C
谢谢
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5