Beijing2011双端队列题解

骑猪看日落 2021-10-23 06:55 356阅读 0赞

**题目链接：[bzoj2457][]**

**挺好的一道题。想了挺长时间。。。**

**如果我们对于每一个读入的数据进行处理，判断每个数据应该放入哪一个队列，或者是应不应该再重新开一个队列，是非常困难的。因为在处理每一个数据时，由于我们不知道之后数据的情况，所以就不能确定当前数据的位置。而且通过观察也没有什么结论性的东西挖掘。。。（行吧我承认，仅仅是我想不出来而已。。或许真的存在呢。。。）**

**那么，我们应该换一种思路去解决：从问题的答案出发，寻找原数据与目标数据之间的联系。**

**首先，容易发现，每一个双端队列里的元素都是单调递增的，且它们的并集就是原数据从小到大排序后的结果（似乎说了一句废话。。。。），所以问题就转化为了：对于一个序列，将其分成若干个连续的子段，使得子段总数量最小。**

**由于双端队列只可以进行对头入队，队尾出队两种操作，所以对于最终答案的每一个子段，在某位置一定存在一个最小的下标，并且这个数的左边和右边的数的下标都是依次非递减的。**

**有了这个性质之后容易证明：我们只需要使从前往后的每一个子段包含的元素尽量多，就可以保证最终的子段的总个数最小。**

**那么做法就显而易见了：先对所有数据排序，同时保留所有数据对应至原数组的下标，然后从前往后寻找最长的“单谷函数”，最终得到的所有“单谷函数”的个数就是最终的答案。**

**其实问题到这里并没有结束。。我们忽略了相等元素的情况。对于相等的元素，它们在子段当中的位置是可以随意变化的，所以我们可以通过改变这些元素的相对位置来得到一个更优的解。**

**具体的处理方式是这样（如果我们用pair来存下每个元素的大小以及坐标，那么sort排序完之后，所有相等的元素的下标就是递增排好的）：**

**1.O（m）（m为相同元素的个数）时间复杂度求出一段相同元素下标的最大值max\_a和最小值min\_a。**

**2.判断之前元素的下标last处于“单谷函数”的上升段还是下降段。**

**3.如果是上升段，如果last<min\_a，那么直接将所有元素加入上升段；如果last>min\_a，直接开一个新的“单谷函数”，这样并不会影响最终答案的正确性。**

**4.同理，如果是下降段，比较last与max\_a的大小关系并判断即可。**

**代码就很简单了：**

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int SIZE=200010;
    typedef pair<int,int> PII;
    PII a[SIZE];
    int n;
    
    int main() {
        scanf("%d",&n);
        for (int i=0;i<n;++i) {
            int x;
            scanf("%d",&x);
            a[i]=make_pair(x,i);
        }
        sort(a,a+n);
        int last=n,ans=1;
        bool flag=false;
        int i=0;
        while (i<n) {
            int j=i;
            while (a[i].first==a[j].first) j++;
            j--;
            int max_a=a[j].second,min_a=a[i].second;
            if (min_a>last&&(flag)) i=j+1,last=max_a;
            else if (min_a<last&&(flag)) {
                i=j+1;
                last=min_a;
                flag=false;
                ans++;
            }
            else if (max_a<last&&(!flag)) i=j+1,last=min_a;
            else if (max_a>last&&(!flag)) {
                i=j+1;
                last=max_a;
                flag=true;
            }
        }
        printf("%d",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/ABBEJ/p/11330063.html

[bzoj2457]: https://www.lydsy.com/JudgeOnline/problem.php?id=2457