临沧市住房和城乡建设局网站,郑州妇科,wordpress 会员登录,外国风格网站建设用途【题目来源】https://www.acwing.com/problem/content/description/136/【题目描述】 达达现在碰到了一个棘手的问题#xff0c;有 N 个整数需要排序。 达达手头能用的工具就是若干个双端队列。 她从 1 到 N 需要依次处理这 N 个数#xff0c;对于每个数#xff0c;达达能做…【题目来源】https://www.acwing.com/problem/content/description/136/【题目描述】 达达现在碰到了一个棘手的问题有 N 个整数需要排序。 达达手头能用的工具就是若干个双端队列。 她从 1 到 N 需要依次处理这 N 个数对于每个数达达能做以下两件事 1. 新建一个双端队列并将当前数作为这个队列中的唯一的数 2. 将当前数放入已有的队列的头之前或者尾之后。 对所有的数处理完成之后达达将这些队列按一定的顺序连接起来后就可以得到一个非降的序列。 请你求出最少需要多少个双端序列。【输入格式】 第一行输入整数 N代表整数的个数。 接下来 N 行每行包括一个整数 Di代表所需处理的整数。【输出格式】 输出一个整数代表最少需要的双端队列数。【数据范围】 1≤N≤200000【输入样例】 6 3 6 0 9 6 3【输出样例】 2【算法代码】
#include bits/stdc.h
using namespace std;const int N2e55;
typedef pairint,int PII;
PII a[N];
int n;int main() {cinn;for(int i0; in; i) {cina[i].first;a[i].secondi;}sort(a,an);int i0,lastn1,ans1;int dir-1; //dir is used to record directionswhile(in) {int ji1;while(jn a[j].firsta[i].first) {j;}int minxa[i].second;int maxxa[j-1].second;if(dir-1) { //dir-1 indicates declineif(lastmaxx) lastminx;else {dir1; //dir1 indicates increaselastmaxx;}} else {if(lastminx) lastmaxx;else {ans;lastminx;dir-1;}}ij;}coutansendl;return 0;
}/*
in:
6
3
6
0
9
6
3out:
2
*/
【参考文献】https://www.cnblogs.com/Horb7/p/15603051.htmlhttps://www.acwing.com/solution/acwing/content/7210/https://www.acwing.com/solution/content/27971/
