BZOJ 2457 双端队列

Sherry 现在碰到了一个棘手的问题，有Ｎ个整数需要排序。

Sherry 手头能用的工具就是若干个双端队列。

她需要依次处理这 N 个数，对于每个数， Sherry 能做以下两件事：

1．新建一个双端队列，并将当前数作为这个队列中的唯一的数；

2．将当前数放入已有的队列的头之前或者尾之后。

对所有的数处理完成之后， Sherry 将这些队列排序后就可以得到一个非降的序列。

Input第一行包含一个整数 N ，表示整数的个数。接下来的 N 行每行包含一个整数 D_i ，其中 D_i 表示所需处理的整数。Output

其中只包含一行，为 Sherry 最少需要的双端队列数。

Sample Input

6 3 6 0 9 6 3

Sample Output

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<vector>
 8 #include<queue>
 9 //#include<stack>
10 //#include<map>
11 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
12 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
13 #define Ii inline int
14 #define Iv inline void
15 #define Il inline long long
16 #define Ib inline bool
17 #define INF 0x7ffffff
18 #define re register
19 #define ll long long
20 #define Max(a,b) ((a)>(b)?(a):(b))
21 #define Min(a,b) ((a)<(b)?(a):(b))
22 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))
23 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
24 #define Fill(a,b) memset((a),(b),sizeof((a)))
25 #define D_e_Line printf("
-------------
");
26 #define D_e(x) printf("
______%d_______
",x)
27 #define Pause system("pause")
28 using namespace std;
29 const int N=200005;
30 Ii read(){
31     int s=0,f=1;char c;
32     for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
33     while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
34     return s*f;
35 }
36 template<class Tp>Iv print(Tp x){
37     if(x<0)putchar('-'),x=-x;
38     if(x>9)print(x/10);
39     putchar(x%10^'0');
40 }
41 #define down 0
42 #define up 1
43 struct node{
44     int w,id;
45     bool operator< (const node a)const{
46         if(w!=a.w)return w<a.w;
47         return id<a.id;
48     }
49 }a[N<<1];
50 int mx[N],mi[N];
51 int main(){
52     int n=read(),cnt=0,flag=up,tmp=INF,ans=0;
53     R(i,1,n)
54         a[i]=(node){read(),i};
55     sort(a+1,a+n+1);
56     R(i,1,n)
57         if(i==1||a[i].w!=a[i-1].w)
58             mx[cnt]=a[i-1].id,
59             mi[++cnt]=a[i].id;
60     mx[cnt]=a[n].id;
61     R(i,1,cnt){
62         if(flag==down){
63             if(tmp>mx[i])
64                 tmp=mi[i];
65             else
66                 tmp=mx[i],flag=up;
67         }
68         else if(flag==up){
69             if(tmp<mi[i])
70                 tmp=mx[i];
71             else
72                 flag=down,tmp=mi[i],++ans;
73         }
74     }
75     print(ans);
76     return 0;
77 }

View Code