题目描述

达达现在碰到了一个棘手的问题，有N个整数需要排序。 达达手头能用的工具就是若干个双端队列。 她从1到N需要依次处理这N个数，对于每个数，达达能做以下两件事： 1．新建一个双端队列，并将当前数作为这个队列中的唯一的数； 2．将当前数放入已有的队列的头之前或者尾之后。 对所有的数处理完成之后，达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。 请你求出最少需要多少个双端序列。 输入格式 第一行输入整数N，代表整数的个数。 接下来N行，每行包括一个整数Di,代表所需处理的整数。 输出格式 输出一个整数，代表最少需要的双端队列数。 数据范围 1≤N≤200000 输入样例： 6 3 6 0 9 6 3 输出样例： 2

题解

逆向思维：两个性质：

最后合并的双端队列一定是有序的。最后的双端队列中每一个双端队列储存元素的的下标一定满足单峰形状。

因此题目转化为在一个排好序的序列中，找到若干段在原序列中下标满足单峰形状的序列。

代码

#include <iostream> #include <limits.h> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 200010; PII a[N]; int main() { int n; cin >> n; for(int i = 0; i < n; i++) { cin >> a[i].first; a[i].second = i; } sort(a, a + n); int res = 1; for(int i = 0, last = n + 1, dir = -1; i < n;) { int j = i; while(j < n && a[j].first == a[i].first) j++; int maxp = a[j - 1].second, minp = a[i].second; if(dir == -1) { if(last > maxp) last = minp; else dir = 1, last = maxp; } else { if(last < minp) last = maxp; else { res++; dir = -1; last = minp; } } i = j; } cout << res << endl; return 0; }