题解：P15027 [UOI 2021 II Stage] 优美数组

· · 题解

P15027 [UOI 2021 II Stage] 优美数组 题解

题目传送门

题目描述

很多人都以为哥萨克胡子最喜欢的数字是七。然而，他们错了。实际上他最喜欢的数字是二。正因如此，他只喜欢那些恰好包含两个不同数字的数组。

尽管如此，普通的那种只包含两个不同数字的数组在他看来还是太过混乱，而哥萨克讨厌混乱。所以，他只喜欢那些任意两个相邻元素都互不相同的数组。

正式地说，要使一个数组令胡子满意，需要满足以下条件：

例如，他喜欢数组 [1, 4, 1, 4, 1]。这个数组只包含两个不同的数字 1 和 4。并且没有两个相邻的数字值相同。但是他不喜欢数组 [1, 4, 5]（因为有三个不同的数字）、[1, 1, 1, 1, 1]（因为有相同的相邻元素，并且只有一个数字）、[7, 7, 6, 6]（因为有相同的相邻元素）。

给定一个包含 n 个整数 a_1, a_2, \dots, a_n 的数组 a。你需要修改最少数量的数字，使得这个数组能让哥萨克胡子满意。找出这个最少修改数量。

例如，在数组 [1, 1, 1, 1, 1] 中，需要将第二个和第四个元素改为任意其他数字。因此在这个例子中，答案是 2。

输入格式

第一行包含一个整数 n (1 \leq n \leq 10^5) —— 数组中的数字个数。

第二行包含 n 个整数 a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^9) —— 数组中的数字。

输出格式

输出需要修改的最少数字数量，以使数组符合哥萨克的喜好。

做法分析

先计算出奇数位和偶数位数量最大和的二的的数字个数和数字，然后进行特判。

如果一共只有两种或一种不同的数。

如果只有一种不同的数字。

总数等于数量的一半。

如果有两种不同的数字。

总数是数量减次数最大值。

否则。

总数是数量减次数最大值。

代码

#include<bits/stdc++.h>
#define endl '\n'
#define kuaitou ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define baoliu(n) fixed<<setprecision(n)
using namespace std;
int main(){
    kuaitou;
    int n;
    cin>>n;//输入
    if(n==1){//如果只有一个数
        cout<<"0";
        return 0;
    }
    int a[n+1]={};
    map<int,int>mp1,mp2;//不同数字和个数
    for(int i=1;i<=n;i++){
        cin>>a[i];//输入
        if(i%2==0){//如果是偶数位
            mp1[a[i]]++;//增加
        }else{//如果是奇数位
            mp2[a[i]]++;//增加
        }
    }
    pair<pair<int,int>,pair<int,int>> MAX1={{0,-1e9},{0,-1e9}},MAX2={{0,-1e9},{0,-1e9}};//前两大的数字，和最大数字出现个数
    for(auto y:mp1){//偶数位前两大的数字，和最大数字出现个数
        if(MAX1.first.second<y.second){
            if(MAX1.second.second<y.second){
                MAX1.first.second=MAX1.second.second;
                MAX1.first.first=MAX1.second.first;
                MAX1.second.second=y.second;
                MAX1.second.first=y.first;
            }else{
                MAX1.first.second=y.second;
                MAX1.first.first=y.first;
            }
        }
    }
    for(auto y:mp2){//奇数位前两大的数字，和最大数字出现个数
        if(MAX2.first.second<y.second){
            if(MAX2.second.second<y.second){
                MAX2.first.second=MAX2.second.second;
                MAX2.first.first=MAX2.second.first;
                MAX2.second.second=y.second;
                MAX2.second.first=y.first;
            }else{
                MAX2.first.second=y.second;
                MAX2.first.first=y.first;
            }
        }
    }
    int ans=0;
    //如果如果一共只有两种或一种不同的数。
    if(MAX1.first.first==0||MAX2.first.first==0){
        if(MAX1.first.first==0&&MAX2.first.first!=0){
            if(MAX1.second.first==MAX2.second.first){
                ans=n-(MAX1.second.second+MAX2.first.second);
            }else{
                ans=n-(MAX1.second.second+MAX2.second.second);
            }
        }else if(MAX2.first.first==0&&MAX1.first.first!=0){
            if(MAX2.second.first==MAX1.second.first){
                ans=n-(MAX2.second.second+MAX1.first.second);
            }else{
                ans=n-(MAX2.second.second+MAX1.second.second);
            }
        }else{
            if(MAX1.second.first==MAX2.second.first){
                ans=n/2;
            }else{
                ans=n-(MAX1.second.second+MAX2.second.second);
            }
        }//否则
    }else if(MAX1.second.first==MAX2.second.first){
        if(MAX1.second.second==MAX2.second.second){
            if(MAX1.first.second==MAX2.first.second){
                ans=n-(MAX1.first.second+MAX1.second.second);
            }else{
                ans=n-(MAX1.second.second+max(MAX1.first.second,MAX2.first.second));
            }
        }else if(MAX1.second.second>MAX2.second.second){
            ans=n-(MAX1.second.second+MAX2.first.second);
        }else{
            ans=n-(MAX2.second.second+MAX1.first.second);
        }
    }else{
        ans=n-(MAX1.second.second+MAX2.second.second);
    }
    cout<<ans;//输出答案
    return 0;//完结散花
}

AC记录