【uva1610】PartyGames（算法效率--构造dfs）

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 using namespace std;
 7 
 8 const int N=1010,L=510;
 9 int n;
10 char s[L];
11 struct node{char s[L];int l;}a[N];
12 
13 bool cmp(node x,node y) {return strcmp(x.s,y.s)<0;}
14 void bfs(int x,int y,int i)
15 {
16     if (i>a[y].l&&i>a[x].l) return;//&&
17     int t;
18     if (i'A';
19     else t=0;
20     for (int j=t;j<26;j++)
21     {
22       s[i]='A'+j;
23       if (strcmp(a[x].s,s)<=0 && strcmp(a[y].s,s)>0) return;
24     }
25     s[i]='A'+t;//
26     bfs(x,y,i+1);
27 }
28 int main()
29 {
30     while (1)
31     {
32       scanf("%d",&n);
33       if (!n) break;
34       for (int i=1;i<=n;i++)
35       {
36         scanf("%s",a[i].s);
37         a[i].l=strlen(a[i].s);
38       }
39       sort(a+1,a+1+n,cmp);
40       memset(s,'\0',sizeof(s));
41       int x=(1+n)/2,y=x+1;
42       bool ok=false;
43       int t=0;
44       for (int i=0;i)
45       {
46         int u=a[x].s[i]-'A',v=a[y].s[i]-'A';
47         if (u!=v) {bfs(x,y,i); break;}
48         s[i]=a[x].s[i];
49       }
50       printf("%s\n",s);
51     }
52     return 0;
53 }