额。。。。。突然想起来，这两天忘了写博客了。。。。。这题就是拖布排序，维护连续n个数字的和sum，越晚拿出来的sum越大，晚拿出来减早拿出来的就是‘+’了
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <vector> using namespace std; const int maxn=20; int sum[maxn],c[maxn]; int t,n; string aa; vector<int> bb[maxn]; void addage(int x,int y) { c[y]++; bb[x].push_back(y); } void mmp() { int b=0; queue<int> q; for(int i=0;i<=n;i++) if(!c[i]) q.push(i); while(q.size()) { int md=q.size(); for(int i=0;i<md;i++) { int mm=q.front(); q.pop(); sum[mm]=b; for(int j=0;j<bb[mm].size();j++) { int mmm=bb[mm][j]; c[mmm]--; if(c[mmm]==0) q.push(mmm); } } b++; } } void init() { memset(c,0,sizeof(c)); for(int i=0;i<=n;i++) bb[i].clear(); memset(sum,0,sizeof(sum)); } int main() { scanf("%d",&t); while(t--) { init(); scanf("%d",&n); cin >> aa; int nn=0; for(int i=0;i<=n;i++) for(int j=i+1;j<=n;j++) { if(aa[nn]=='+') addage(i,j); else if(aa[nn]=='-') addage(j,i); nn++; } mmp(); for(int i=1;i<=n;i++) { printf("%d",sum[i]-sum[i-1]); if(i!=n) printf(" "); else printf("\n"); } } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7413675.html
相关资源：数据结构—成绩单生成器