题意: 给定一个只包含小写字母的字符串, 你可以修改任意位置的字符 (变换为 a-z 中任一个)
然后重新排列字符串. 现在要求用最少次数的修改得到一个回文串, 若有多种方案, 输出字典序最小的方案.
对于长度为偶数的字符串显然好说
我们只需开一个桶记录下 a-z 分别有多少个
偶数个的前后分别输出 个数 / 2 次 即可
奇数个的两两匹配, 分别输出前面的 个数 / 2+1 次, 输出后面的的 个数 / 2 次 即可
对于长度为奇数的的字符串我们发现有一部分字符串是不输出的 (被替换掉的)
我们在不输出的中 和 剩余的唯一的奇数个字符中找最小的填入序列中间即可
实现如下:
- #include <algorithm>
- #include <iostream>
- #include <cmath>
- #include <cstring>
- #include <map>
- #include <string>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <cstdio>
- #include <cstdlib>
- using namespace std;
- typedef long long ll;
- inline int read()
- {
- register int p(1),a(0);register char ch=getchar();
- while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
- if(ch=='-') p=-1,ch=getchar();
- while(ch>='0'&&ch<='9') a=a*10+ch-48,ch=getchar();
- return a*p;
- }
- const int N=200010;
- char a[N],cun[N];
- int n,book[30],dan[N],ge,ji,all=0,us=0,fla;
- int main()
- {
- // freopen("input","r",stdin);
- // freopen("output","w",stdout);
- scanf("%s",a+1);n=strlen(a+1);
- for(int i=1;i<=n;i++) book[a[i]-'a']++;
- for(int i=0;i<26;i++) if(book[i]&1) dan[++ge]=i;
- for(int i=0;i<26;i++) all+=book[i];
- if(all&1)
- {
- cun[(n>>1)+1]='a'+dan[(ge>>1)+1];
- book[dan[(ge>>1)+1]]--;ge--;
- }
- for(int i=0;i<26;i++)
- {
- for(int j=(book[i]>>1);j>=1;j--)
- {
- ++us;
- cun[n-us+1]=cun[us]='a'+i;
- }
- if(book[i]&1)
- {
- ++ji;
- if(ji<=ge)
- {
- ++us;
- cun[n-us+1]=cun[us]='a'+i;
- ge--;
- }
- }
- }
- for(int i=1;i<=n;i++) printf("%c",cun[i]);
- return 0;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-2875575.html