题目描述(Google Kickstart2021 Round A Problem A)
Charles 将一个字符串的优良分数定义为,在 1≤i≤N/2 的范围内,满足 Si≠SN−i+1 的 i 的数量(索引从 1 开始)。
例如,字符串 CABABC 的优良分数为 2,因为 S2≠S5 并且 S3≠S4。
Charles 给了 Ada 一个长度为 N 的由大写字母构成的字符串 S,并让她将其转换为一个优良分数为 K 的字符串。
每次操作,Ada 都可以将字符串中的任意一个字符转换为任意一个大写字母。
请你帮助 Ada 确定,将给定字符串 S 转换为优良分数为 K 的字符串,所需要的最少操作次数。
样例
输入样例
2
5 1
ABCAA
4 2
ABAA
输出样例
Case #1: 0
Case #2: 1
数据范围
全部数据:1≤T≤100,0≤K≤N/2。
测试点 1 (小数据测试点):1≤N≤100。
测试点 2 (大数据测试点):最多不超过 10 组数据满足,1≤N≤2×10^5,其余数据满足,1≤N≤100。
解题思路
对每次查询 $O(n)$
- 字符串对半开找到不对称的就记录即可;
- 注意下对半开的下标就行;
#include<iostream>
using namespace std;
int main(){
int t, n, k;
string s;
cin>>t;
for(int x = 1; x <= t; ++x){
cin>>n>>k;
cin>>s;
int cnt = 0;
for(int i = 0; i < n/2; ++ i)
if(s[i] != s[n-i-1])
++cnt;
int y = cnt >= k ? cnt-k : k-cnt;
printf("Case #%d: %d\n", x, y);
}
return 0;
}