Uva 140 Bandwidth

#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;

}

刘汝佳代码

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

©著作权归作者所有：来自51CTO博客作者Rign的原创作品，如需转载，请注明出处，否则将追究法律责任