网站建设托管产品图,学院网站建设的需求分析,深圳百度首页优化,苏宁推客如何做网站栈
jzoj 2295
题目大意#xff1a;
有一个A数组#xff0c;一个B数组和一个栈#xff0c;现在把A数组的数存入栈#xff08;操作1#xff09;#xff0c;然后再从栈中取出来放在B数组#xff0c;但取出可以从栈顶#xff08;操作2#xff09;#xff0c;也可以从栈…栈
jzoj 2295
题目大意
有一个A数组一个B数组和一个栈现在把A数组的数存入栈操作1然后再从栈中取出来放在B数组但取出可以从栈顶操作2也可以从栈底操作3现在问怎样操作可以使B数组的字典序最小
输入样例
5
1 4 3 5 2输出样例
1 2 4 3 5数据范围
对于10%的数据n⩽5n \leqslant 5n⩽5; 对于30%的数据n⩽1000n \leqslant 1000n⩽1000; 对于100%的数据n⩽100000n \leqslant 100000n⩽100000保证给出的AiA_iAi是1∼n1\sim n1∼n 的一个排列;
样例解释
依次使用操作 1、2、1、1、1、1、2、3、3、2 可以得到样例输出 1 2 4 3 5 。
解题思路
因为要求的是字典序最小的所以我们每一个数字都要尽量小我们可以拿的有栈的两端和A数列剩下的所有数剩下的数求最大可以用ST表我们选最小的如果选的是A数列剩下的数中最小的那我们让这个数前面的数全部入栈
代码
#includecmath
#includecstdio
#includecstring
#includeiostream
using namespace std;
const int MAXX100500;
int n,w,l,r,bg,s1,s2,minn,a[MAXX],p[MAXX],f[MAXX][20],s[MAXX][20];
void js(int l,int r)//查询ST表
{if (lr){minnMAXX;return;}int klog(r-l1)/log(2);if (f[l][k]f[r-(1k)1][k]){minnf[l][k];//最小值ws[l][k];//位置}else{minnf[r-(1k)1][k];ws[r-(1k)1][k];}
}
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d,a[i]);f[i][0]a[i];s[i][0]i;}int tlog(n)/log(2)1;for (int j1;jt;j)//建ST表for (int i1;in-(1j)1;i)if (f[i][j-1]f[i(1(j-1))][j-1]){f[i][j]f[i][j-1];s[i][j]s[i][j-1];}else{f[i][j]f[i(1(j-1))][j-1];s[i][j]s[i(1(j-1))][j-1];}l1;r0;bg1;a[0]MAXX;for (int i1;in;i){while(p[l]lr) l;//去掉选过的while(p[r]lr) r--;if (lr) s1a[l],s2a[r];//判断栈是否为空else s1s2MAXX;js(bg,n);if (minns1minns2)//lr表示栈的范围bg表示A序列的开始位置{printf(%d ,minn);p[w]1;//记录bgw1;//A序列的开始位置在这个点后面1rw-1;//前面的全部入栈}else if(s1s2)//从栈底取出{printf(%d ,s1);p[l]1;l;}else{printf(%d ,s2);//从栈顶取出p[r]1;r--;}}
}
