【贪心】Bzoj 2457:[BeiJing2011]双端队列

2457: [BeiJing2011]双端队列

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 209 Solved: 95
[Submit][Status][Discuss]

Description

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

HINT

100%的数据中N≤200000。

　　先简化一拨题意。

　　大约是说有这样多个双端队列用。

　　然后队列有序。

　　队列内元素有序。

　　问最多几个能满足最后的序列有序。

　　我们先排序一遍，按两个关键字，第二个关键字是数组位置从大到小。

　　发现样例的位置序列如此:3 1 6 2 5 4

　　仔细想一想

　　队列里面的元素必须连续

　　大约一个队列能处理一段的要求是pos 从大到小然后到最低从小到最大。

　　一个这样的折点大约就用一个队列

　　当然还有特殊情况——相等的数。

　　相等的数显然可以放在一个队列中....因为我可以控制其递增或递减，于是只需要记录最大值和最小值，然后当成一个整体就好。

　　贪心+模拟的时候：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5  
 6 #define maxn 200100
 7  
 8 using namespace std;
 9  
10 struct node{
11     int x,pos;
12 }a[maxn];
13  
14 int mx[maxn],mi[maxn];
15  
16 inline int in()
17 {
18     int x=0,f=1;char ch=getchar();
19     while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
20     if(ch=='-')f=-1,ch=getchar();
21     while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
22     return x*f;
23 }
24  
25 bool cmp(const node A,const node B){return A.x<B.x||(A.x==B.x&&A.pos<B.pos);}
26  
27 int main()
28 {
29     int n,cnt=0,ans=0,h=99999999,b=1;
30     n=in();
31     for(int i=1;i<=n;i++)a[i].x=in(),a[i].pos=i;
32     sort(1+a,1+a+n,cmp);
33     for(int i=1;i<=n;i++)
34         if(i==1||a[i].x!=a[i-1].x)
35         {
36             mx[cnt]=a[i-1].pos;
37             mi[++cnt]=a[i].pos;
38         }
39     mx[cnt]=a[n].pos;
40     for(int i=1;i<=cnt;i++)
41     {
42         if(!b)
43         {
44             if(h>mx[i])h=mi[i];
45             else h=mx[i],b=1;
46         }
47         else{
48             if(h<mi[i])h=mx[i];
49             else h=mi[i],b=0,ans++;
50         }
51     }
52     printf("%d",ans);
53     return 0;
54 }
55

View Code