#include<bits/stdc++.h>using namespace std;int id[30];char letter[10];int main(){ //数据输入 char input[1000]; while(scanf("%s",input) == 1 && input[0]!='#'){ int n=0; for(char tmp='A';tmp<='Z';tmp++) if(strchr(input,tmp)!=NULL){ id[tmp-'A']=n++; letter[id[tmp-'A']]=tmp; } int len=strlen(input),p=0,q=0; vector<int>u,v; while(true){ while(p < len && input[p] !=':') p++; if(p==len) break; while(q < len && input[q] != ';') q++; for(int i=p+1;i<q;i++){ u.push_back(id[input[p-1]-'A']); v.push_back(id[input[i]-'A']); } p++;q++; } //处理 int P[10],bestP[10],pos[10],ans=n; for(int i=0;i<n;i++) P[i]=i; do{ for(int i=0;i<n;i++) pos[P[i]]=i; int wid=0; for(int i=0;i<u.size();i++) wid=max(wid,abs(pos[u[i]]-pos[v[i]])); if(wid<ans) {ans=wid;memcpy(bestP,P,sizeof(P));} }while(next_permutation(P,P+n)); for(int i=0;i<n;i++) cout<<letter[bestP[i]]<<" "; cout<<"-> "<<ans<<endl; } return 0;}

刘汝佳代码

简单总结就是全排列然后计算当前最小带宽