思路讲解
idxrare指出现次数最少的，idxmost指出现次数最多的字母
A[idxrare]=A[idxmost];
然后好了。
AC代码
多用sort啦，宁愿多耗点空间，这样能够确保你的意志能够被准确地执行
唉，前面在遍历的时候瞎搞，唉。
https://codeforces.com/contest/2047/submission/294578039
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
cin>>n;
vector<char> A(n+10);
map<char,ll> cntCh;
if(n==1){
string s;
cin>>s;
cout<<s<<endl;;
continue;
}
for(int i=1;i<=n;++i){
cin>>A[i];
if(cntCh.count(A[i]))
cntCh[A[i]]+=1;
else
cntCh[A[i]]=1;
}
ll mostOcc=0,rareOcc=17;
char most='0',rare='0';
vector<pair<ll,char> > chCnt;
for(map<char,ll>::iterator it=cntCh.begin();it!=cntCh.end();it++){
chCnt.emplace_back(it->second,it->first);
}
sort(chCnt.begin(),chCnt.end());
ll idxmost=0,idxrare=0;
for(int i=1;i<=n;++i){
if(A[i]==chCnt.back().second)
idxmost=i;
if(A[i]==chCnt.front().second)
idxrare=i;
}
A[idxrare]=A[idxmost];
for(int i=1;i<=n;++i){
cout<<A[i];
}
cout<<endl;
}
return 0;
}
|
心路历程（WA，TLE，MLE……）
暴力（当然，会超时）
注意next_permutation()如果想遍历全部的话需要sort一下啦。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;
inline ll cntDiffS(string s,ll i,ll j){
ll res=0;
s[i]=s[j];
sort(s.begin(),s.end());
set<string> judrepeat;
do{
if(!judrepeat.count(s)){
++res;
judrepeat.insert(s);
}
}while (next_permutation(s.begin(), s.end()));
return res;
}
inline string change(string s,ll i,ll j){
s[i]=s[j];
return s;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
cin>>n;
string s;
cin>>s;
vector<pair<ll,string> > ans;
if(n==1){
cout<<s<<endl;
continue;
}
for(int i=0;i<n-1;++i){
for(int j=1;j<n;++j){
if(i==j)
continue;
if(s[i]==s[j])
continue;
ans.emplace_back(cntDiffS(s,i,j),change(s,i,j));
}
}
sort(ans.begin(),ans.end());
cout<<ans.back().second<<endl;
}
return 0;
}
|