COJ1170(A Simple Problem)

这题题目是A simple problem，但这题可谓A的不简单，不知道WA了多少次！

题目大意：给定一个数列，求最长的连续子数列，使得最大值与最小值之差不超过给定值。

由于数据量比较大，暴力法复杂度为O(N)，肯定挂掉。我的做法如下：

在扫描的过程中，当发现一段数的最大值与最小值之差大于给定值时，设最小值与最大值下标分别为i,j(无大小关系)，下一次扫描时则从MIN(i,j)+1开始，这样可以避免很多不必要的计算。具体实现时要用到单调队列，纠结之处在于把下标移动和队列头指针移动搞混了！这题还有一点需要注意的地方就是最大值减最小值可能溢出。下面的代码提交时需改数据类型。

View Code

 1 #include <stdio.h>
 2 #define MAX(a,b) ((a)>(b)?(a):(b))
 3 #define N 1000001
 4 int a[N];
 5 int q1[N],q2[N];
 6 int front1,front2,rear1,rear2;
 7 int main()
 8 {
 9     int i,j,n,k,min,max,ans;
10     while(~scanf("%d%d",&n,&k))
11     {
12         front1=rear1=0;
13         front2=rear2=0;
14         ans=1;
15         for(i=j=0;i<n;i++)
16         {
17             scanf("%d",&a[i]);
18             while(front1<rear1&&a[i]<=a[q1[rear1-1]])   rear1--;
19             q1[rear1++]=i;
20             while(front2<rear2&&a[i]>=a[q2[rear2-1]])   rear2--;
21             q2[rear2++]=i;
22             min=a[q1[front1]];
23             max=a[q2[front2]];
24             if(max-min>k)
25             {
26                 ans=MAX(ans,i-j);
27                 if(a[i]==max)
28                 {
29                     while(max-a[q1[front1+1]]>k)    front1++;
30                     j=q1[front1++]+1;
31                 }
32                 else
33                 {
34                     while(a[q2[front2+1]]-min>k)    front2++;
35                     j=q2[front2++]+1;
36                 }
37             }
38             else if(i==n-1) ans=MAX(ans,i-j+1);
39         }
40         printf("%d\n",ans);
41     }
42     return 0;
43 }