练习string
最小变换次数下，且字典序最小输出回文串。
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <iostream> 5 #include <algorithm> 6 #include<deque> 7 #include<vector> 8 using namespace std; 9 const double eps = 1e-8; 10 const double PI = acos(-1.0); 11 const int maxn=200010; 12 string st; 13 int cnt[maxn]; 14 deque<char> qu; 15 vector<int> odd; 16 17 int main() 18 { 19 cin>>st; 20 memset(cnt,0,sizeof(cnt[0])); 21 for(int i=0; i<st.size(); i++) 22 { 23 cnt[st[i]]++; 24 } 25 for(int i='a'; i<='z'; i++) 26 { 27 if(cnt[i]%2) 28 odd.push_back(i); 29 } 30 sort(odd.begin(),odd.end()); 31 int l=0; 32 int r=odd.size()-1; 33 while(l<r) 34 { 35 cnt[odd[l]]++; 36 cnt[odd[r]]--; 37 l++; 38 r--; 39 } 40 for(int i='a'; i<='z'; i++) 41 { 42 if(cnt[i]%2) 43 { 44 cnt[i]--; 45 qu.push_back(i); 46 break; 47 } 48 } 49 for(int i='z'; i>='a'; i--) 50 { 51 while(cnt[i]) 52 { 53 qu.push_back(i); 54 qu.push_front(i); 55 cnt[i]-=2; 56 } 57 } 58 while(qu.size()) 59 { 60 cout<<qu.front(); 61 qu.pop_front(); 62 } 63 cout<<endl; 64 return 0; 65 }