正如lyd所说，和数据结构本身没什么太大关联

题意

中文题面

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

思路

反方向思考

先排序好，原来的位置跟着排序

要满足双端队列，需要满足排序之后的原位置要先递减，再递增

不满足的话开新的双端队列

代码

#include<cstdio> #include<algorithm> #include<vector> #define N 200005 #define INF 0x3fffffff using namespace std; int n; pair<int, int>a[N]; vector<int>p[N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i].first); a[i].second = i; } sort(a + 1, a + 1 + n); int t = 0; for (int i = 1; i <= n; i++) { p[++t].push_back(a[i].second); while (a[i].first == a[i + 1].first) p[t].push_back(a[++i].second); } for (int i = 1; i <= t; i++) sort(p[i].begin(), p[i].end()); bool flag = 0; int num = INF, ans = 1; for (int i = 1; i <= t; i++) { int s = p[i].size(); if (flag) { if (num < p[i][0]) num = p[i][s - 1]; else { ++ans; flag = 0; num = p[i][0]; } } else { if (num > p[i][s - 1]) num = p[i][0]; else { flag = 1; num = p[i][s - 1]; } } } printf("%d\n", ans); return 0; }

 

转载于:https://www.cnblogs.com/lincold/p/10162098.html

相关资源：JAVA上百实例源码以及开源项目