数学建模社区-数学中国
标题:
求大牛给个高效算法
[打印本页]
作者:
气态水
时间:
2011-12-28 21:11
标题:
求大牛给个高效算法
boj 11841
; B/ c* n) \( A2 K" y4 N$ b
北邮开崛史
0 i0 H; ~8 G! T
Star it!
1 \4 N0 @2 m; ]$ M4 n
9 k( B k! X# ?/ |! z
Submit: 196 Accepted:33
! b8 p: q" t% V: a
Time Limit: 5000MS Memory Limit: 65536K
# E* Z% T0 T7 U6 ^# M9 |5 D- d
Description
4 G; B, d8 A! h% P5 B1 ~7 l
北京邮电大学到了2155年的时候已经发展到了一个难以想象的程度，不仅在国内有着响亮的名号，在国际上也成了各国学子梦寐以求的学习圣地，为了更好地满足教学要求，学校决定在火星上建立分校区（当然那个时候地球早住不下那么多人了，没办法啊，只要跑到火星上去了），同时为了纪念200周年的校庆，学校决定为北邮的历代校长建立纪念碑（当然包括我们的林校长），但是土地上坑坑洼洼的（没办法啊，火星毕竟是火星），堪查队事先把地表的情况都堪测好了，他们把地表数据用海拔高度表示，保存在了一个数组A之中，现在要求找出一块最长的空地，但得在这空地上最高海拔高度与最低海拔高度之差不超过一个M值，这样的土地便于工程队去规整。但是对于没有学过计算机科学与技术的工程队，这样大的计算量早就超出了他们的能力范围，好在当时他们得到了热心的火星人的帮助才解决了这一大问题。那现在，你做为热心的火星人，用你高超的计算能力去解决这一问题吧。
, Q5 g3 @- t. B, @# U
8 m8 w1 F$ @; x& y* L
Input
% @6 F) T; n3 W0 u# h
第一行为两个整数N和M，N.为记录地表数据数组中数据的总数，M为要求的高度差。
7 `' `. o/ T7 B4 {1 H# T8 P& S* R
第二行为地表数据数组A，有N个整数，每两个整数之间用空格隔开，其中A[i] < 100000000;
0 H8 w7 ^7 F( A' R7 d* M( G4 ~' q. p: b v
1 < N <= 1000000;
* N1 n: X5 K& s3 Q
M < 1000000;
( H* s8 M% r0 V3 A
& d( L0 Q; B4 G- Y4 O) H4 _
. S$ m/ R' O+ E# `& A5 Z
Output
# v# M( N$ x. Z
一个整数LEN，表示在地表数据数组中，求最长的连续的一段，并且该段里面的最大值和最小值之差不大于M。
2 T1 r) v, @+ b# Z8 n) W7 C
LEN为那段的长度。
: p5 l" y; J/ p0 C' m; @; ]
+ r1 n* a `3 C3 z/ ]3 ?$ v4 @! u' d
9 {% ]% {" c* N
Sample Input
. k% h+ O* k1 C
( ~; A+ X- t" A# W$ Y
10 5
4 p' T) j) j, T2 m' @
1 5 7 3 5 2 2 2 1 7
3 g: s# _6 Z8 e
; ?1 a; A# s' j: ~
: U3 L3 x+ c7 m( {) Z' c0 Q
Sample Output
! [; j4 ?' [* z8 p5 ]
; r i: |; d7 a. e5 x$ w4 n
7
' k$ K7 p* j" {- B! }5 Y6 y
$ A j: h+ L p6 L
8 h/ _. B0 M5 x! X. w& w' s& I1 U& E
Hint
/ p+ |$ O1 ?, a* W9 _# p
SAMPLE中，从2到8这段中，最大值为7，最小值为2，他们之间的差为5，且他们是最长的一段。
, J8 V) m3 x/ h9 r9 A/ w9 _4 o
7 P9 I+ V7 \/ d! K2 J0 T L
我用暴力，结果超时了
4 U3 D* Z, U' Q6 h1 H
请大牛个个算法
6 \; Q( k! p( F4 V6 G4 w" B* a
最好附上核心代码~~
" _4 r+ T% v/ [3 |+ Y7 e) \) V8 R9 P
谢谢
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5