26. 不相同的字符串（第一期模拟笔试）

题目：样例：

输入

1 abab

输出

2

思路：

        这里的题目要求我们要最少操作删除次数，我们可以先统计每个字符个数，然后开始删除，每操作删除一次，就会产生一个新字符，ans += r[i] >> 1  就是我们操作次数，然后记得操作过后剩余的字符个数是多少，最后统计一下我们操作完成后，剩余的有多少个 0 位，然后判断我们 产生 ans 个字符后可不可以补完，不可以就累加我们之后继续多余的操作数，就是我们最少操作数。

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;string s;
inline void solve()
{cin >> s;vector<int>r(26,0);	// 记录字符个数for(auto i : s){++r[i - 'a'];	// 开始统计}int ans = 0;	// 最少操作次数int cnt = 0;	// 记录字符个数是 0 的总数// 遍历 26 个字母字符for(int i = 0;i < 26;++i){// 如果有字符超过 1 了，那么开始删除if(r[i] > 1){// 累加删除操作次数ans += r[i] >> 1;// 计算删除后的字符个数r[i] = r[i] - ((r[i] >> 1) << 1);}}// 统计 删除过后字符个数是 0 的有多少个for(int i = 0;i < 26;++i){if(!r[i]) ++ cnt;}// 如果删除两个字符产生的新字符超过 空余字符个数的// 这里 ans - cnt 是补 0 位后剩余，// 然后就是我们拿两个删 补一个的操作次数，加上我们之前的操作次数 ans if(ans > cnt) ans = ans + (ans - cnt);// 输出答案cout << ans << endl;
}signed main()
{
//	freopen("a.txt", "r", stdin);___G;int _t = 1;cin >> _t;while (_t--){solve();}return 0;
}

最后提交：