「BZOJ 2457」双端队列

Sherry 现在碰到了一个棘手的问题，有 N 个整数需要排序。
Sherry 手头能用的工具就是若干个双端队列。
她需要依次处理这 N 个数，对于每个数， Sherry 能做以下两件事：

1. 新建一个双端队列，并将当前数作为这个队列中的唯一的数；
2. 将当前数放入已有的队列的头之前或者尾之后。
   对所有的数处理完成之后， Sherry 将这些队列排序后就可以得到一个非降的序列。

BZOJ

分析

正着不好做，我们考虑反着做。

我们先将数列排好序。易知双端队列显然是排序后的数列的一部分，于是我们记录原来的下标值，那么下标值的低谷一定是它所在的队列中第一个加入的元素，然后从这个元素开始，它前面的数的下标值显然要是递减的，后面的数要是递增的才能加入这个双端队列，于是我们找到低谷，把它两端的递增或递减的数加到这个双端队列里，递增或递减用个标记讨论一下就好了。

注意到有些元素可能相同，所以它们排序后的位置可以交换，我们找到一个顺序使低谷最少，只需记录一个最大的下标值和最小的下标值即可。

代码

//=========================
//  author:tyqs
//  date:2019.12.3
//  website:http://tyqs.kim
//=========================
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 200003
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

int n, lst, ans;
int d[N], r[N];
bool flg;

bool cmp(int x, int y) { return d[x] < d[y]; }

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(d[i]), r[i] = i;
    sort(r + 1, r + 1 + n, cmp), sort(d + 1, d + 1 + n);
    for (int i = 1; i <= n; ++i) {
        int p = i, mx = r[i], mn = r[i];
        while (d[p] == d[p+1]) mx = max(mx, r[p+1]), mn = min(mn, r[p+1]), p++;
        if (!flg) {
            if (mx < lst) lst = mn;
            else lst = mx, flg = 1;
        }
        else {
            if (mn > lst) lst = mx;
            else lst = mn, ans++, flg = 0;
        }
        i = p;
    }
    printf("%d", ans);
    return 0;
}

「BZOJ 2457」双端队列

原文：https://www.cnblogs.com/hlw1/p/12260602.html