Codeforces Round 867 (Div3) E + 摩尔投票算法

题目链接： https://codeforces.com/problemset/problem/1822/E
题目大意：
求变成“反回文串”的最小次数。
思路：
我们先来看看它的要求， , 比如我有 5 个字符，要求第 3 个和第 5-3+1 个字符不同，很显然这是不可能的。所以对于奇数长度的字符串，这个要求不能满足。
再观察一下还有什么情况不满足要求，对于 cccccc 这样的字符串无论怎么交换都不能满足要求，这可以是一种情况，再来观察一下，cccccb 呢？也不可以，我们来找找可以满足要求的最多的 c 的数量，cccbbb ,所以当一个字符出现的次数大于 n/2 时也是无解的。
好了，那对于一个偶数长度的字符串我们如何去交换，使得其操作次数最小又能满足要求呢？我们应该去交换两个不满足要求的字符，这样实现两两交换，去尽可能减少操作次数。
我们先用map根据字符来当下标，把所有回文对的下标存起来，来求得最多的字符数。
然后遍历数组（这里只需要遍历一半），去求得需要修改得字符数。和
代码：

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define x first
#define y second
void solve()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    map<char,int>mp;
    if(s.size()%2){
        cout<<"-1"<<endl;
        return;
    }
    int ans=0;
    for(int i=0;i<n;i++)
    {
        mp[s[i]]++;
        ans=max(ans,mp[s[i]]);//记录字符出现的最大次数
    }
    if(ans*2>n){
        cout<<"-1"<<endl;
        return;
    }
    mp.clear();
    int res=0;
    ans=0;
    for(int i=0;i<n/2;i++)
    {
        if(s[i]==s[n-i-1])//这里数组下标是从0开始的所以把加一换成减一
        {
            res++;
            ans=max(ans,++mp[s[i]]);//找出对称位置上相同字符中出现次数最多的那个字符的出现次数
        }
    }
    cout<<max(ceil(res*1.00/2),ans*1.0)<<endl;
}
signed main(){
	IOS
	int t;
    cin>>t;
	while(t--)
	{
		solve();
	}
}

注意一下：max 在使用时两个数据类型要相同，不可以是 (double, int)。

知识点补充

以上代码中用到了 ceil 函数，作用是对浮点数进行向上取整。所以有乘 1.0 的操作。

摩尔投票算法

其核心思想是：如果一个元素出现的次数在数组中超过一半，那么该元素的出现次数一定大于其他元素的出现次数之和。
这个算法的核心是“计数抵消”，让不同元素相互抵消，最终筛选出候选元素，再通过验证确认是否为目标。
分为两个阶段：
候选阶段（投票）：先选数组第一个元素为候选元素，count = 1。
之后遍历数组元素，1）若当前元素与候选元素相同：count++；2）若当前元素与候选元素不同：count–；
当计数 count 减为 0 时，更换候选元素为当前元素，并将 count 重置为1。
验证阶段（验票）：遍历结束后，候选元素是 “可能的多数元素”，但需要再次遍历数组，统计其实际出现次数。若实际次数超过总元素数的一半，则确认为主元素；否则说明不存在主元素（这里说明，如果题目已经标注明确存在多数元素的情况下可以省略）
这个统计多数可以通过桶来计数。

Acwing 4547. 伊格内修斯和公主IV

看一道模板题吧。
链接：[https://www.acwing.com/problem/content/description/4550/
思路：摩尔投票算法，和上方思路一致

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=1e6+5;
void solve()
{
    int n;
    while(cin>>n)
    {
        int cnt=0,ans=0,a,lst=0;
        while(n--)
        {
            cin>>a;
            if(a==lst)cnt++;
            else{
                if(!cnt)lst=a,cnt=1;//数组开头第一个数，或者是计数cnt减到0时更换主元素。
                else cnt--;//不一致时cnt--
            }
        }
        cout<<lst<<endl;
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

欢迎关注我的微信公众号呀微信公众号文章链接