水果网页制作模板,百度快照优化网站,秦皇岛哪里能做网站,WordPress留言板dux来源#xff1a;牛客网 文章目录题目描述题意#xff1a;题解#xff1a;代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 131072K#xff0c;其他语言262144K
64bit IO Format: %lld题目描述
Tom最近在研究一个有趣的排序问…来源牛客网
文章目录题目描述题意题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 131072K其他语言262144K
64bit IO Format: %lld题目描述
Tom最近在研究一个有趣的排序问题。如图所示通过2个栈S1和S2Tom希望借助以下4种操作实现将输入序列升序排序。
操作a如果输入序列不为空将第一个元素压入栈S1 操作b如果栈S1不为空将S1栈顶元素弹出至输出序列
操作c如果输入序列不为空将第一个元素压入栈S2
操作d如果栈S2不为空将S2栈顶元素弹出至输出序列
如果一个1~n的排列P可以通过一系列操作使得输出序列为12…(n-1)nTom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列a,c,c,b,a,d,d,b
当然这样的操作序列有可能有几个对于上例(1,3,2,4)a,c,c,b,a,d,d,b是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
输入描述: 第一行是一个整数n。 第二行有n个用空格隔开的正整数构成一个1~n的排列 输出描述: 共一行如果输入的排列不是“可双栈排序排列”输出数字0否则输出字典序最小的操作序列每两个操作之间用空格隔开行尾没有空格。 示例1 输入 复制
4
1 3 2 4输出 复制
a b a a b b a b示例2 输入 复制
4
2 3 4 1输出 复制
0示例3 输入 复制
3
2 3 1输出 复制
a c a b b d备注:
30%的数据满足n10
50%的数据满足n50
100%的数据满足n1000题意
有四种操作问如何操作可以实现将输入序列升序排序 四种操作分别是 操作a如果输入序列不为空将第一个元素压入栈S1 操作b如果栈S1不为空将S1栈顶元素弹出至输出序列 操作c如果输入序列不为空将第一个元素压入栈S2 操作d如果栈S2不为空将S2栈顶元素弹出至输出序列
题解
貌似二分图可以做不过我还没看懂 首先推出规律 如果两个数 i,j(i≤j)i,j(i≤j) 不能被放入同一个栈中当且仅当存在 k,kjk,kj, 且 q[k]q[i]q[j]q[k]q[i]q[j]。 现在有两个栈我们只需要将满足这个条件的点各自归到一边中间连一条线用经典的染色法判断是否为二分图若是则按照颜色入栈 若不是则说明不能完成
代码
#includecstdio
#includecstdlib
#includeiostream
#includealgorithm
#includestack
#includecmath
#define maxn 1004
using namespace std;const int inf19260817;
int n,num;
int color[maxn];
int t[maxn]; //要排序的元素的存储
int s[maxn]; //判断两个数字是否满足规则
bool flag,e[maxn][maxn];void paint(int x,int c){ //DFS进行染色color[x]c;for(int i1;in;i){if(e[x][i]){ //查找相邻点 if(color[i]c) flagfalse; //若相邻点颜色相同则错误if(!color[i]) paint(i,3-c); //若未染过色对其染色3-c结果为1,2表示1与2号栈}}
}void make(){ //创造二分图s[n1]inf; for(int in;i1;i--){s[i]t[i];if(s[i1]s[i])s[i]s[i1];}for(int i1;in;i){for(int ji1;jn;j){if(t[i]t[j] s[j1]t[i]){e[i][j]e[j][i]1; //按规则创建图}}}for(int i1;in;i){ if(!color[i]){ //染色paint(i,1);}}
}void work(){if(flagfalse){printf(0\n);return ; }stackint stack1,stack2;int now1;for(int i1;in;i){if(color[i]1){ //入栈stack1.push(t[i]);printf(a ); }else {stack2.push(t[i]);printf(c ); }while((!stack1.empty() stack1.top()now) || (!stack2.empty() stack2.top()now)){ //判断是否弹出if(!stack1.empty() stack1.top()now){stack1.pop();now;printf(b );}else{stack2.pop();now;printf(d ); }}}
}int main(){flag1;scanf(%d,n);for(int i1;in;i){scanf(%d,t[i]);}make();work(); return 0;
}
