要保证变化次数最少就是出现次数为奇数的相互转化,而且对应字母只改变一次。保证字典序小就是字典序大的字母变成字典序小的字母。

长度n为偶数时候,次数为奇数的有偶数个,按照上面说的搞就好了。

n为奇数时,要考虑最后中间那个字母。交换法可以证明,其实是贪心最后没有转化掉的字母。

#include<bits/stdc++.h>
using namespace std; typedef long long ll; const int LEN = 2e5+;
char s[LEN]; int cnt[]; //#define LOCAL
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
gets(s);
int i = , j;
for(; s[i]; i++){
cnt[s[i]-'a']++;
}
int n = i;
i = ; j = ;
while(i < j){
if((cnt[i]&) && (cnt[j]&)) cnt[i++]++,cnt[j--]--;
else {
if(cnt[i]&^) i++;
if(cnt[j]&^) j--;
}
}
int md = -;
if(n&) md = i;
j = ;
for(i = ; i < ; i++){
cnt[i] >>= ;
while(cnt[i]--){
s[j++] = i+'a';
}
}
if(n&){
s[j++] = md+'a'; s[j] = ;
printf("%s",s);
for(i = j-; i >= ; i--) putchar(s[i]);
}
else {
s[j] = ;
printf("%s",s);
for(i = j-; i >= ; i--) putchar(s[i]);
}
puts("");
return ;
}

最新文章

  1. Docker知识-1
  2. ng-repeat循环出来的部分调用同一个函数并且实现每个模块之间不能相互干扰
  3. HTML5 3D爱心动画 晚来的七夕礼物
  4. phoenix 开发API系列(一)创建简单的http api
  5. Android动画学习笔记-Android Animation
  6. Java集合中Map接口的使用方法
  7. buffer正确的拼接方式
  8. 无法将类型为“System.Windows.Controls.SelectedItemCollection”的对象强制转换为类型“System.Collections.Generic.IList`1
  9. C#中的转换
  10. 用VS2005开发WinCE程序调试图文教程
  11. Azure中国版 制作镜像 捕捉镜像
  12. C#/.NET使用HttpWebRequest、SqlBulkCopy从API获取数据批量插入DB
  13. mvc_ajax_for form
  14. (转载)delphi实例TDBGrid用右键菜单复制行粘贴行
  15. CSS3初步
  16. 给线程发送消息让它执行不同的处理(自己建立消息循环,非常有意思) good
  17. 关于GPUImage的导入
  18. CentOS 7下安装vertica记录
  19. The frist email to myself by python
  20. python迭代和解析(3):range、map、zip、filter和reduce函数

热门文章

  1. ABC118D(DP,完全背包,贪心)
  2. Baidu - Echarts 地图实例测试,并绘制平滑圆弧路径
  3. 51nod1035(循环节)
  4. 洛谷P1053 篝火晚会
  5. 记录一下我的三天清明节假期,TP5.1写企业站
  6. 小程序启用slot -- 传入 wxml标签
  7. 如何使用JMETER从JSON响应中提取数据
  8. python入门之进程与线程
  9. 转 基于MySQL MEB的备份恢复
  10. CodeForces - 95B