题目链接:https://codeforces.com/contest/1822/problem/E
被hack了。
错误的地方:每次取两个最大的,然后直接消去,这里不对,比如:2,3,3。
正解:还是每次取两个最大的,但这两个最大的每次只消去1,因为总共的数量不会超过\(1e5\),所以时间复杂度很低。
代码:
#include <bits/stdc++.h>
using namespace std;
int same[30];
int cnt[30];
void solve(){
for (int i=1;i<=26;i++) same[i] = 0,cnt[i] = 0;
int n;
cin>>n;
string s;
cin>>s;
s = ' '+s;
int ans = 0;
if (n&1) cout<<-1<<'\n';
else{
for (int i=1;i<=n/2;i++){
if (s[i]==s[n-i+1]){
same[s[i]-'a'+1]++;
}else{
int a = s[i]-'a'+1,b = s[n-i+1]-'a'+1;
for (int j=1;j<=26;j++){
if (j!=a&&j!=b) cnt[j]++;
}
}
}
int cc = 0;
int mx = 0;
int id = 0;
for (int i=1;i<=26;i++) {
cc += same[i];
if (mx<same[i]){
mx = max(mx,same[i]);
id = i;
}
}
cc -= mx;
if (cc<=mx){
ans += cc;
mx -= cc;
if (cnt[id]>=mx) ans += mx;
else ans = -1;
}else{
if ((cc-mx)&1){
ans = 1;
ans += (cc-mx-1)/2+mx;
}else{
ans = (cc-mx)/2+mx;
}
}
cout<<ans<<'\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
cin>>T;
while(T--) solve();
return 0;
}