最小字典序（stack）
输入序列中有 n 个正整数，栈 S 开始为空。
你每次只可以进行下面两种操作之一：① 将输入序列头端的数据移至 S 栈顶（进 S 栈）；
② 将 S 栈顶元素输出并删除（退 S 栈）。
当然，输入序列非空时才可进行①操作，S 非空时才可进行②操作。
当①和②的操作都无法执行时，一定得到 n 个数据的一个输出序列。
由于①和②混搭的次序不同，导致相应的输出序列也各不相同，
请你求出能够得到的输出序列中字典序最小的一个序列。所谓字典序最小可以这样理解：首元素尽量小，在首元素最小的序列中第二元素尽可能小、在前 2 数据字典序最小的序列中，第三项尽可能小…，直至 n 项全部排完。
【输入输出说明】
输入文件 stack.in 第一行仅有一个正整数 n，表示输入序列中数据的个数。
第二行就是输入序列中依次排列的 n 个数据，相邻两数据间有一个空格。
输出文件 stack.out 中仅有一行 n 个数，就是字典序最小的输出序列，相邻整数间用一个空格隔开。
【输入输出样例】
stack.in:
4
2 3 1 4
stack.out:
1 3 2 4
【样例说明】
得到最小字典序的操作序列为：①①①②②②①②
【数据说明】
60%的数据 n<12；
80%的数据 n<1000；
100%的数据 n<100000,其他数据在 int 范围。
首先我们发现题目是区赛的第二个题，按照往年的惯例，第二个题以贪心模拟为主
而因为要求按照字典序输出，很明显应该满足前面的数尽可能小
于是我们得到了贪心思路：
（1）因为输入序列是单向的，所以可以使用一个idx表示当前处理到第几位
（2）每次查找从前往后最小的数，在这个数的位置压栈
（3）首先弹出第一个数，之后判断每一个栈顶的数是否小于后面最小的数
（4）若栈顶等于后面最小的数，因为输入序列是单向的，所以应该尽可能先弹出前面的数
（5）为了节约时间，初始化book数组，用book[i]表示第i个数至第n个数之间最小的数的最小编号（可以利用递推实现）
上代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<stack> #define _ 0 #define olinr return #define love_nmr 0 using namespace std; int n,a[100050],book[100050],idx; int main() { freopen("stack.in","r",stdin); freopen("stack.out","w",stdout); int i,j; stack<int> s; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); book[n]=n; for(i=n-1;i>=1;i--) { if(a[i]<=a[book[i+1]])book[i]=i; else book[i]=book[i+1];//初始化，若第i-1位置的数小于从第i至第n位置的数则更新book[i-1]，否则延续 } bool flag=false;//判断是否首位 while(1) { if(idx==n+1) { while(!s.empty()) { printf("%d ",s.top()); s.pop(); } return 0; }//处理到输入序列最后一位，全部弹出 if(!flag)idx=1,flag=true; for(i=idx;i<=book[idx];i++)s.push(a[i]);//压栈 idx=i;//更新idx if(!s.empty()) { printf("%d ",s.top()); s.pop();//弹出栈顶 } while(!s.empty()&&s.top()<=a[book[idx]]) { printf("%d ",s.top()); s.pop();//继续弹出 } } olinr ~~love_nmr-(0^_^0); }
比赛的时候就得了50分
后来发现把a[book[idx]]打成了book[idx] Q_Q