Wave

T3 Wave

題目描述

給定一個長為n的數列，試求一個最長的不穩定波動子序列滿足任意偶數項的值不小于其相鄰兩項的值，且相鄰兩項的差不小于k。

輸入輸出格式

輸入格式：

輸入第一行兩個正整數n,k。

第二行n個非負整數描述這個數列。

輸出格式：

輸出一個整數即為答案。

輸入輸出樣例

輸入樣例#1：

10 3

2 6 7 9 0 3 7 6 4 4

輸出樣例#1：

5

說明

對于20%的資料,n<=10^3

對于70%的資料,n<=10^5

1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<ctime>
 7 #include<set>
 8 #include<map>
 9 #include<stack>
10 #include<cstring>
11 #define inf 2147483647
12 #define For(i,a,b) for(register int i=a;i<=b;i++)
13 #define p(a) putchar(a)
14 #define g() getchar()
15 //by war
16 //2017.11.2
17 using namespace std;
18 int n,k;
19 int a[2000010];
20 int b[2000010];
21 int cnt;
22 
23 void in(int &x)
24 {
25     int y=1;
26     char c=g();x=0;
27     while(c<'0'||c>'9')
28     {
29     if(c=='-')
30     y=-1;
31     c=g();
32     }
33     while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+c-'0',c=g();
34     x*=y;
35 }
36 void o(int x)
37 {
38     if(x<0)
39     {
40         p('-');
41         x=-x;
42     }
43     if(x>9)o(x/10);
44     p(x%10+'0');
45 }
46 int main()
47 {
48     in(n),in(k);
49     in(a[1]);
50     b[++cnt]=a[1];
51     For(i,2,n)
52      {
53          in(a[i]);
54          if(cnt&1)
55          {
56              if(a[i]-b[cnt]>=k)
57              b[++cnt]=a[i];
58              else
59              if(a[i]<b[cnt])
60              b[cnt]=a[i];
61         }
62         else
63         {
64             if(b[cnt]-a[i]>=k)
65              b[++cnt]=a[i];
66              else
67              if(a[i]>b[cnt])
68              b[cnt]=a[i];
69         }
70      }
71      o(cnt);
72      return 0;
73 }