思维好题
题目大意：给你一个1-n的排列，要求你用两个栈将这个排列排成升序，无解输出0
看起来非常不可做，，，
先考虑只有一个栈
我们弹掉栈顶当且仅当栈顶<后面所有元素的最小值
比如说:
top=1,当前后面的序列为4,6
我们此时将栈顶弹出排序是正确的
若top=5,当前后面的序列为4,6
我们若将5此时弹出，后面的4无论怎么弹都会在5后面，不合法，GG
当我们扩展到两个栈，两个栈出栈策略是固定的，所以本题的关键就在将数分到两个栈中
怎么分
考虑有一个结论：
若两个数a[i],a[j](i<j)不能在一个栈中，当且仅当存在k>j,使得a[k]<a[i]<a[j]
通俗来讲就是两个条件：
-
前面的小于后面的
-
后面的后面还有比前面的小的数
比如： 4 6 3 如果4,6在一个栈内，那么按照最开始的策略，4没有办法被弹掉，进而6进栈会在4上面，错误
于是记录一个后缀最小值，找出所有满足上面条件的点对，连边跑二分图染色
为什么是二分图呢？因为二分图一个集合内部是没有连边的，而只有集合与另一个集合有连边，上面的第一个第二个栈刚好和二分图不谋而合
我好菜....
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<stack> 7 #define re register int 8 #define ll long long 9 #define maxn 3005 10 using namespace std; 11 int a[maxn]; 12 stack<int>s1; 13 stack<int>s2; 14 string ans=""; 15 int n; 16 struct node{ 17 int u,v,nxt; 18 }e[maxn<<1]; 19 int head[maxn],cnt; 20 void add(int u,int v){ 21 e[++cnt].u=u; 22 e[cnt].v=v; 23 e[cnt].nxt=head[u]; 24 head[u]=cnt; 25 } 26 int vis[maxn]; 27 void dfs(int u,int col){ 28 vis[u]=col; 29 for(re i=head[u];i;i=e[i].nxt){ 30 int v=e[i].v; 31 if(!vis[v])dfs(v,3-col); 32 else if(vis[v]==vis[u]){ 33 printf("0 "); 34 exit(0); 35 } 36 } 37 } 38 int mmin[maxn]; 39 int now=1; 40 int main(){ 41 memset(mmin,0x3f,sizeof(mmin)); 42 scanf("%d",&n); 43 for(re i=1;i<=n;i++)scanf("%d",&a[i]); 44 for(re i=n;i>=1;i--) 45 mmin[i]=min(a[i],mmin[i+1]); 46 for(re i=1;i<=n;i++) 47 for(re j=i+1;j<n;j++){ 48 if(a[i]<a[j]&&mmin[j+1]<a[i])add(i,j),add(j,i); 49 } 50 for(re i=1;i<=n;i++) 51 if(!vis[i])dfs(i,1); 52 for(re i=1;i<=n;i++){ 53 if(vis[i]==1){ 54 s1.push(a[i]); 55 printf("a "); 56 } 57 else { 58 s2.push(a[i]); 59 printf("c "); 60 } 61 while(1){ 62 if(!s1.empty()&&s1.top()==now){ 63 s1.pop(); 64 printf("b "); 65 now++; 66 } 67 else if(!s2.empty()&&s2.top()==now){ 68 s2.pop(); 69 printf("d "); 70 now++; 71 } 72 else break; 73 } 74 } 75 76 return 0; 77 }