[HYSBZ 2457] 双端队列

双端队列

Time Limit: 1 Sec Memory Limit: 128 MB

Description

Sherry现在碰到了一个棘手的问题，有Ｎ个整数需要排序。 Sherry手头能用的工具就是若干个双端队列。她需要依次处理这N个数，对于每个数，Sherry能做以下两件事： 1．新建一个双端队列，并将当前数作为这个队列中的唯一的数； 2．将当前数放入已有的队列的头之前或者尾之后。对所有的数处理完成之后，Sherry将这些队列排序后就可以得到一个非降的序列。

Input

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

Output

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

Sample Input

6 3 6 0 9 6 3

Sample Output

2

HINT

100%的数据中 N ≤ 200000。

分析：

最开始把这道题想复杂了，想到了昨天做的双栈排序，企图直接用数学推什么关系的三个数不能同时存在于一个栈。但是实现有难度，并且时间复杂度太高。

这道题容易局限于队列这一结构中，实际上没有必要真的构造这一数列。

实际上正解是通过“Sherry将这些队列排序后就可以得到一个非降的序列”，想到直接排序后再考虑相邻的数能否组成一个区间。

1.什么样的数能组成一个区间呢？

S={a₁,a₂,a₃ ...a_i-1,a_i,a_i+1... a_n-1,a_n}

=> {a₁} => {a₁,a₂,a₃} => {a₅,a₄,a₁,a₂,a₃}

=>{a_i,a_i-1,a_i-3,a_i-2,a_i+1,a_i+2}

由此可知：若排序后的下标组成了“谷形”，即先递减，再递增。

2.如何处理相同的数？相同数的下标可以互换，从而影响结果。

此时采用贪心策略，将不同的数分为不同的区间，把同一区间数的下标尽量按上一区间的增减顺序递增或递减排列。以上图为例，S={3,1,6,2,5,4},划分区间后则得到S={{3},{1,6},{2,5},{4}}。同一区间中的数顺序可以互换。

当前一区间为递增时，如果这一区间的最小值小于分界点，则变为单调递减。

当前一区间为递减时，如果这一区间的最大值大于分界点，则变为单调递增。

sort(a+1,a+1+n,cmp);
a[0].order = 0xfffffff;//根据之后的判断条件预处理边界
a[n+1].num = 0xfffffff;
bool rise = 0;
int ans = 0;
int j = 0;//j记录分界点

for(int i=1;i<=n;i++)
{
    if(rise)
    {
        bool fl = 0;//记录是否改变增减性
        if(a[i].order < a[j].order)rise = 0,j = i,fl = 1;
        while(a[i].num == a[i+1].num)i++;
        if(!fl)j = i;
    }
    else
    {
        int p = i;//若此区间为单调递减，增减性并未改变，则此时的i代表了最小值
        while(a[i].num == a[i+1].num)i++;
        if(a[i].order > a[j].order)rise = 1,j = i,ans++;
        else j = p;
    }
}
    
if(!rise)ans++;//如果最后为单调递减，并未形成谷形，同样算一个独立的队列