青龙网站建设,北京建设工程交易服务中心网站,wordpress英文导航模板,wordpress popular posts怎么用http://codeforces.com/problemset/problem/600/C#xff1b; 题意#xff1a;给你一个小写字母组成的英文串#xff0c;将它转换为回文串#xff0c;要求#xff0c;改变的字母的个数最小#xff0c;移动字母不算改变字母。 所得的串字典序是最小的。最后输出所得到的串… http://codeforces.com/problemset/problem/600/C 题意给你一个小写字母组成的英文串将它转换为回文串要求改变的字母的个数最小移动字母不算改变字母。 所得的串字典序是最小的。最后输出所得到的串。 思路要求改变的字母数最小那么用贪心的思想就把原来的字母尽可能多的填入要求的串中。 首先先把原串中的字母统计出来开个数组存对应的字符的个数然后从‘a’开始循环如果对应字母的个数大于1 如果是偶数个的话就在所求串两端一边加一个可以正好加完若是奇数个的话那么按这样的操作最后就剩下一个那么把它加入队列。 最后操作队列中的单个的然后补一个加到串的两端直到串被补满。 然后再对串的一半排下序就可以了。 1 #includestdio.h2 #includealgorithm3 #includeiostream4 #includestring.h5 int cmp(const void*p,const void*q);6 char a[100005*2];7 char b[100005*2];8 char c[100005*2];9 char bb[100005*2];10 int aa[26];11 #includequeue12 using namespace std;13 int main(void)14 {15 int n,i,j,k,p,q,l,z;16 while(scanf(%s,a)!EOF)17 {18 queueintque;19 z0;20 memset(aa,0,sizeof(aa));21 lstrlen(a);22 for(i0; il; i)//统计对应的字母有多少个23 {24 aa[a[i]-a];25 }26 int t0;27 for(i0; i26; i)28 {29 if(aa[i]!0)30 {31 if(aa[i]2)//大于2的先加在串的两端32 {33 while(aa[i]1)34 {35 aa[i]-2;36 a[t]ia;37 a[l-1-t]ia;38 t;39 z2;40 }41 }42 if(aa[i]1) que.push(i);//剩下1的入队43 44 }45 46 47 }48 while(!que.empty())49 {50 int fque.front();51 que.pop();52 if(zl)53 {54 break;55 }56 while(aa[f]0)57 {58 aa[f]-2;59 a[t]fa;60 a[l-1-t]fa;61 t;62 z2;63 if(zl)64 {65 break;66 }67 }68 if(zl)//当满了就跳出69 {70 break;71 }72 }73 int uu;74 if(l%20)//找串的一半分奇数偶数讨论75 {76 uul/2;77 }78 else uu(l-1)/2;79 for(i0; iuu; i)80 {81 b[i]a[i];82 }83 qsort(b,uu,sizeof(char),cmp);//对串的一半排序84 for(i0; iuu; i)85 {86 printf(%c,b[i]);87 }88 if(l%21)89 {90 printf(%c,a[(l)/2]);91 }92 for(iuu-1; i0; i--)93 {94 printf(%c,b[i]);95 }96 printf(\n);97 98 }99 return 0;
100 }
101 int cmp(const void*p,const void*q)
102 {
103 char *w(char*)p;
104 char *u(char*)q;
105 return (*w-a)-(*u-a);
106 } 转载于:https://www.cnblogs.com/zzuli2sjy/p/5008089.html
