2018.9.26 2018NOIP冲刺之栈
最小字典序(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