首页 > 代码库 > NOIP2008 双栈排序 染色+模拟
NOIP2008 双栈排序 染色+模拟
挺不错的一道题,首先可以知道若存在形如 k<i<j 但 a[k]<a[i]<a[j]这样的,那么i,j一定不能(从始至终不能)进入同一个栈 例如 2 3 1,若2 3进入同一个栈,那么1再进栈然后马上出栈,这时候,2没有办法在3之前出来。
所以对于这样的i,j我们连一条边,然后dfs染色,若染色中发现相邻点颜色相同,则无解,否则我们按照1,2,1,2的顺序染色。
确定了每一个数属于哪个栈后,用2个stack模拟一下就好了。
#include <iostream> #include <stack> #include <algorithm> #include <cstdio> #include <vector> using namespace std; int n,top=1,a[1005],mins[1005],belong[1005],need[1005]; vector<char> ans; vector<int> v[1005]; stack<int> s1; stack<int> s2; bool dfs(int now,int k) { belong[now]=k; for(int j=0;j<v[now].size();j++) { int next=v[now][j]; if(belong[next]==k) return false; if(belong[next]) continue; dfs(next,-k); } return true; } void pop() { while(s1.top()==need[top]||s2.top()==need[top]) { if(s1.top()==need[top]) {printf("b ");top++;s1.pop();} else {printf("d ");top++;s2.pop();} } } void print() { for(int i=1;i<=n;i++) { pop(); if(belong[i]==1) { printf("a "); s1.push(a[i]); } else { printf("c "); s2.push(a[i]); } } pop(); puts(""); } int main() { s1.push(-1); //防止栈空,方便模拟 s2.push(-1); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); need[i]=a[i]; } sort(need+1,need+1+n); mins[n]=a[n]; //预处理i-n的最小值 for(int i=n-1;i>=1;i--) { mins[i]=min(mins[i+1],a[i]); } for(int i=1;i<=n-2;i++) //利用结论建图 { for(int j=i+1;j<=n-1;j++) { if(mins[j+1]<a[i]&&a[i]<a[j]) { v[i].push_back(j); v[j].push_back(i); } } } bool flag=true; for(int i=1;i<=n&&flag;i++) //对每个点染色,确定所属栈 { if(belong[i]) continue; flag=dfs(i,1); } if(flag) print(); else printf("0\n"); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。