方法一：st算法。复杂度O(nlogn)，如果题目给的是10s可以轻松过，5s就难了。
方法二：赤裸裸的单调队列。
维护两个单调队列，一个Qmax单调递减，一个Qmin单调递增。对于这两个队列，如果队列的头的位置与i的距离大于i-m+1，那么丢弃头。每个a[i]进来，维护两个队列的性质，进队。如果Qmax的头的值-Qmin的头的值<阈值，输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| {**************************************************************
Problem: 1342
User: abcdabcd987
Language: Pascal
Result: Accepted
Time:2808 ms
Memory:11944 kb
****************************************************************}
var i,n,m,c,Hmin,Hmax,Tmin,Tmax:longint;
flag:boolean;
Qmin,Qmax,a:array[1..1000001]of longint;
begin
readln(n,m,c);
for i:=1 to n do read(a[i]);
Hmin:=1;Hmax:=1;
Tmin:=1;Tmax:=1;
Qmin[Tmin]:=1;Qmax[Tmax]:=1;
for i:=2 to n do begin
while (Hmin<=Tmin)and(Qmin[Hmin]<i-m+1) do inc(Hmin);
while (Hmin<=Tmin)and(a[Qmin[Tmin]]>=a[i]) do dec(Tmin);
while (Hmax<=Tmax)and(Qmax[Hmax]<i-m+1) do inc(Hmax);
while (Hmax<=Tmax)and(a[Qmax[Tmax]]<=a[i]) do dec(Tmax);
inc(Tmin);inc(Tmax);
Qmin[Tmin]:=i;Qmax[Tmax]:=i;
if (i>=m)and(a[Qmax[Hmax]]-a[Qmin[Hmin]]<=c) then begin
writeln(i-m+1);
flag:=true;
end;
end;
if not flag then writeln('NONE');
end.
|
