首页 > 代码库 > 【uva 1610】Party Games（算法效率--构造 dfs）
【uva 1610】Party Games（算法效率--构造 dfs）
题意：有一个N个字符串（N≤1000,N为偶数）的集合，要求找一个长度最短的字符串（可不在集合内）S，使得集合中恰好一半的串小于等于S，另一半大于S。如果有多解，要求输出字典序最小的解。
解法：本来我是想分析情况用if else实现的，但是细节很多，特别容易错。结果果然如此。╮(╯_╰)╭ 那么便看看搜索行不行，由于要求字典序最小，也就是长度尽量小的情况下字符尽量小。而且要集合中恰好一半的串小于等于S，另一半大于S，也就是排序后>=中间靠左边的串且<中间靠右边的串。那么我们可以对排序后的中间的2个串从前面开始扫，出现不一样的字符时，就枚举‘A‘~‘Z‘，看看是否符合题目条件。如果这个长度的串都不满足，那么就这个位填当前符合条件的最小的字符，再对下一位搜索，也就是像bfs一样每位全部搜索完才到下一位。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 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[x].l) t=a[x].s[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<a[x].l;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 }
【uva 1610】Party Games（算法效率--构造 dfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。