双栈排序题解 FROM CSDN

2023-08-18 18:38:44

发布于：广东

234阅读

0回复

0点赞

解析：
就算知道是二分图染色还是不会TT。
首先考虑怎么判断是否有解。
a [ i ] 和 a [ j ] 不能压入同一个栈（在同一个栈中出现过）⇔ 存在一个k,使得 i < j < k 且 a [ k ] < a [ i ] < a [ j ]
严格证明就比较复杂了，我就说如何感性理解吧（反正在考场上也没几个人会去严格证明）。
因为一个数只能进出一次，k 要排在前面所以弹出 k 时 i 和 j 都在栈里，如果两者在同一个栈弹出后顺序就错误了，然后找不到除这种情况外的反例，于是就这样了。。。
所以如果输入数据不能使得所有限制成立则无解，然后就可以转化成二分图染色来判定，不能在同一个栈中就连边。
关于输出答案，因为要让字典序最小肯定是尽量加在S1里面，实在不行加进S2。
代码:

#include <bits/stdc++.h>
using namespace std;
 
const int Max=1010;
int n,m=1,size,tot1,tot2,p1[Max],p2[Max];
int first[Max],f[Max],num[Max],vis[Max];
struct shu{int to,next,len;}edge[Max*Max];
 
inline int get_int()
{
	int x=0,f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') f=-1,c=getchar();
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x*f;
}
 
inline void build(int x,int y)
{
	edge[++size].next=first[x],first[x]=size,edge[size].to=y;
	edge[++size].next=first[y],first[y]=size,edge[size].to=x;
}
 
inline void pre()
{
	f[n]=num[n];
	for(int i=n-1;i>=1;i--) f[i]=min(f[i+1],num[i]);
	for(int i=1;i<=n;i++)
	  for(int j=i+1;j<=n;j++)
	    if(f[j]<num[i]&&num[i]<num[j]) build(i,j);
}
 
inline bool dfs(int p,int color)
{
	vis[p]=color;
	for(int u=first[p];u;u=edge[u].next)
	{
	  int to=edge[u].to;
	  if(!vis[to]) dfs(to,3-color);
	  else if(color==vis[to]) return 0;
	}
	return 1;
}
 
int main()
{
	n=get_int();
	for(int i=1;i<=n;i++) num[i]=get_int();
	pre();
	for(int i=1;i<=n;i++) if(!vis[i]&&!dfs(i,1)) {puts("0");return 0;}
	for(int i=1;i<=n;i++)
	{
	  if(vis[i]==1)p1[++tot1]=num[i],printf("a ");
	  else p2[++tot2]=num[i],printf("c ");
	  while(m==p1[tot1]||m==p2[tot2])
	  {
	  	if(m==p1[tot1]) tot1--,printf("b ");
	  	else tot2--,printf("d ");
	  	m++;
	  }
	}
	return 0;
}

欢迎加入团队

有帮助，赞一个

去预览

0/2000

全部评论 11

白
1
1

1

1

1

1

1

1

1

1

1

1

1

1
1
1

1
1
1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1
1

1

1

1

1
1
1

1

1

1

1

1

1

1

1

1

1

1

2026-06-07 来自湖南
0
白
1
1
1

1

1

1

1

1
1

1

1

1

1

1

1

1
1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

2026-06-07 来自湖南
0
白
U

SXDXD

2026-06-07 来自湖南
0
白
................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

2026-06-07 来自湖南
0
白
dddddddddddddddddddDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD................................................................................................................................................................................................................................................................................................................................................................

2026-06-07 来自湖南
0
白
.。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

2026-06-07 来自湖南
0
白
66666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666

2026-06-07 来自湖南
0
大锐则则
。。。。。。

2026-04-11 来自福建
0
༺ཌༀཉི 威风の龙 ༃ༀད༻
66
6

2026-03-23 来自浙江
0
1000d=====(￣▽￣*)
666

2026-03-23 来自浙江
0
不会c++的小女孩 🏆
ok

2026-03-10 来自浙江
0