首页 > 双栈排序
开通博客写题解
头像 昵称很长很长真是太好了
发表于 2020-08-06 22:02:51
菜鸡还没学二分图。。。题意：给定一个序列，问能否双栈排序，如果能，请输出字典序最小的方案；操作a：如果输入序列不为空，将第一个元素压入栈S1操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c：如果输入序列不为空，将第一个元素压入栈S2操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列题 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 savage
发表于 2019-09-07 16:21:38
算法知识点: 二分图,栈,染色法,贪心 复杂度： 解题思路： 如果只有一个栈，则整个操作顺序是固定的： 从前往后遍历每个数，每次先将当前数压入栈中，如果后面的所有数均比栈顶元素大，则将栈顶弹出，否则栈顶不能被弹出。 因此，我们只需考虑将每个数分配给哪个栈即 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 zzugzx
发表于 2020-08-06 19:31:49
题目链接 题意：题解： AC代码 /* Author : zzugzx Lang : C++ Blog : blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #d 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 Ray.C.L
发表于 2020-08-07 17:35:58
思路：要使用2个栈操作使得序列升序，我们可以发现当2个数a[i] a[j]不能放入同一个栈中的时候，要满足条件 i<j<k && a[k]<a[i]<a[j]这里呢，我们用dp[i]表示从i开始到结尾的最小值，不能放到同一个栈中我们就把他分开，这样我们要求的就 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 鞠永全
发表于 2020-08-07 21:28:39
每日一题【二分图染色】 题意：给两个栈和一个排列每次可以选择序列的第一个数入任何一个栈或者让任一一个栈顶元素出栈要求出栈顺序为1-n 思路：首先如果我们只有一个栈会要怎么做，2，3，1不是怎么入栈都不行吗？那么我们可以考虑a[k]<a[i]<a[j] k<i<j,此时我们 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 程序蒟蒻
发表于 2020-08-23 20:36:51
看完题解才发现其实就是二分图匹配，好巧妙。。。。 被学弟秀了一脸 #include <bits/stdc++.h> using namespace std; int a[100005]; vector<int> an 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 savage
发表于 2019-08-31 15:11:57
题目描述 Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-08-13 19:02:51
题意：给你一个长度为n的序列，你是否能用两个栈用以下操作进行排序？操作a：如果输入序列不为空，将第一个元素压入栈S1操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c：如果输入序列不为空，将第一个元素压入栈S2操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列不能输出0，能则输出最小字 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 熠丶
发表于 2020-08-07 16:57:22
这里提供二分图染色的解法 两个数 i,j(i≤j)i,j(i≤j) 不能被放入同一个栈中，当且仅当存在 k,k>jk,k>j, 且 q[k]<q[i]<q[j]q[k]<q[i]<q[j]。 有了上述性质后，我们只需将所有满足条件的点分到两个栈中去即可。这一步 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”