数学建模社区-数学中国
标题:
求大牛给个高效算法
[打印本页]
作者:
气态水
时间:
2011-12-28 21:11
标题:
求大牛给个高效算法
boj 11841
: \( s$ f$ J& F" A9 e5 E
北邮开崛史
% P+ ]8 h- D# B% Q- z/ G9 G
Star it!
' ~( x# L6 m' C
9 p! m5 p& h h' A" U
Submit: 196 Accepted:33
0 P& i: F) x; I- ~: M! z! F m' R
Time Limit: 5000MS Memory Limit: 65536K
& J# L/ f: @; u* u
Description
: N% g: M( F9 N' m
北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度，不仅在国内有着响亮的名号，在国际上也成了各国学子梦寐以求的学习圣地，为了更好地满足教学要求，学校决定在火星上建立分校区（当然那个时候地球早住不下那么多人了，没办法啊，只要跑到火星上去了），同时为了纪念200周年的校庆，学校决定为北邮的历代校长建立纪念碑（当然包括我们的林校长），但是土地上坑坑洼洼的（没办法啊，火星毕竟是火星），堪查队事先把地表的情况都堪测好了，他们把地表数据用海拔高度表示，保存在了一个数组A之中，现在要求找出一块最长的空地，但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值，这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队，这样大的计算量早就超出了他们的能力范围，好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在，你做为热心的火星人，用你高超的计算能力去解决这一问题吧。
) r' L0 _( P' u+ v. l
/ s. b* L5 ?# J; _$ |' K
Input
6 @: |6 X1 i* U, [
第一行为两个整数N和M，N.为记录地表数据数组中数据的总数，M为要求的高度差。
8 W# Y. q7 ]9 H7 X' P$ X
第二行为地表数据数组A，有N个整数，每两个整数之间用空格隔开，其中A[i] < 100000000;
$ r, A6 _. m# \
1 < N <= 1000000;
* f+ H& A6 S8 H3 E) b+ ^
M < 1000000;
% s- x) ?6 T3 d+ j& x4 }) H9 S" f
! H% Y' v8 z0 {- J Z" R
' L. |- h1 ^4 E. d& S" [
Output
0 R1 O/ P" f& V6 z: [
一个整数LEN，表示在地表数据数组中，求最长的连续的一段，并且该段里面的最大值和最小值之差不大于M。
y. z& Z4 b/ J; N
LEN为那段的长度。
* }% f- `; ^ u! i+ K# [
8 ^: H) }& M! l+ }6 P. y
* a. L# ]& N$ |/ r. G: B. L7 V# A
Sample Input
% `7 _! F8 Q, D% X
7 A8 U" w- D& f/ H: q5 y" Y
10 5
7 B7 V3 t* V1 L, X
1 5 7 3 5 2 2 2 1 7
' @& }! W& b. ^$ z+ o% |1 u
( i c# h% ?8 c4 s# _
! A8 ]) g7 l. m& r, ?: H2 Z
Sample Output
6 |5 y, ~* C$ d8 Z! L& |3 \
( r2 H$ d. b3 Q6 I
7
5 X1 j! w* m! I: ]+ H
7 s* R1 d# V1 W* }
5 \, E, v2 i" g$ G6 q; ^$ W
Hint
/ s5 D6 m4 K8 N# U/ U$ k6 ]9 A( S
SAMPLE中，从2到8这段中，最大值为7，最小值为2，他们之间的差为5，且他们是最长的一段。
# t9 V. w5 D; k9 r3 s, `
! V6 d& h) Q }7 S J
我用暴力，结果超时了
* N" R8 ~! X- Z
请大牛个个算法
' R9 q! K% n$ M g" q/ J' o
最好附上核心代码~~
$ C) l" n% n! P4 F, p( j
谢谢
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5