http://www.elijahqi.win/2018/02/19/uoj174/
样例一 input
2 3 1 2 3 4 1 3 4 2
output
1 2 3 1 2 3 4
explanation
对于第一组数据，重复入栈、出栈这两个操作三次，即可得到最优解。
对于第二组数据，最优的操作序列如下：入栈，出栈，入栈，入栈，入栈，出栈，打开阀门，出栈。
早晨起来想了想这题 没看题解 xjb写了个o(n)的方法 不到1k 现在暂时uoj rk3 qwq
这是不是用光了我这一天的运气呀qwq
考虑到打印的位置一定是栈头栈尾 还有新的这个数中的一个数根据我thuwc做题的时候想到的一个想法那么显然 我预处理下右端延伸的最小值 每次看右端有没有比我栈头和栈尾的还小的数 如果有我就一直过去把他加入栈里 如果没有就考虑对我的栈进行一些打印操作 一直到 满足我前面的条件则停止
#include<cstdio> #include<algorithm> #define inf 0x3f3f3f3f #define N 110000 using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f; } int T,n,a[N],rm[N],q[N]; int main(){ freopen("uoj174.in","r",stdin); T=read(); while(T--){ n=read();rm[n+1]=inf;int l=1,r=0; for (int i=1;i<=n;++i) a[i]=read(); for (int i=n;i;--i) rm[i]=min(rm[i+1],a[i]); for (int i=1;i<=n;++i){ if (l<=r){ if (a[q[l]]>rm[i]&&a[q[r]]>rm[i]) {q[++r]=i;continue;} while(!(a[q[l]]>rm[i]&&a[q[r]]>rm[i])&&l<=r) if (a[q[l]]<a[q[r]]) printf("%d ",a[q[l++]]); else printf("%d ",a[q[r--]]);q[++r]=i; }else q[++r]=i; } while(l<=r) if (a[q[l]]<a[q[r]]) printf("%d ",a[q[l++]]); else printf("%d ",a[q[r--]]);puts(""); } }