AtCoder题解｜ABC 111C

题目信息 📚

【题目描述】

A sequence $a_1, a_2, …, a_n$ is said to be /\/\/\/ when the following conditions are satisfied:

For each $i = 1, 2, …, n - 2$, $a_i = a_{i+2}$.
Exactly two different numbers appear in the sequence.

You are given a sequence $v_1, v_2, …, v_n$ whose length is even. We would like to make this sequence /\/\/\/ by replacing some of its elements.

Find the minimum number of elements that need to be replaced.

【输入】

The input is given from Standard Input in the following format:

$n$

$v_1$ $v_2$ $\ldots$ $v_n$

【输出】

Print the minimum number of elements that needs to be replaced.

【数据范围】

$2 \leq n \leq 10^5$
$n$ is even.
$1 \leq v_i \leq 10^5$
$v_i$ is an integer.

【输入样例1】

4
3 1 3 2

【输出样例1】

The sequence $3, 1, 3, 2$ is not /\/\/\/, but we can make it /\/\/\/ by replacing one of its elements: for example, replace the fourth element to make it $3, 1, 3, 1$.

【输入样例2】

6
105 119 105 119 105 119

【输出样例2】

The sequence $105, 119, 105, 119, 105, 119$ is /\/\/\/.

【输入样例3】

4
1 1 1 1

【输出样例3】

The elements of the sequence $1, 1, 1, 1$ are all the same, so it is not /\/\/\/.

【题目来源】

https://atcoder.jp/contests/abc111/tasks/arc103_a

题目解析 🍉

【题目分析】

统计奇数位以及偶数位上所有数字出现的次数（map），从大到小排序（将 map 的 key:value 键值对存入 vector<pair<int, int>> 中，自定义 sort 参数实现按 value 排序），然后贪心即可。

PS：注意奇数位和偶数位上最多出现的数字可能相同，此时需要考虑选择出现次数第二多的情况。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, v[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;

    // 读入数据，并且统计奇数位、偶数位数字出现个数，存入m1, m2中
    map<int, int> m1, m2;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        if (i & 1) m1[v[i]]++;
        else m2[v[i]]++;
    }

    // 将map中的键值对存入vector<pair<int, int>>中，实现按照value排序
    vector<PII> v1, v2;
    for (auto t: m1) v1.push_back({t.first, t.second});
    for (auto t: m2) v2.push_back({t.first, t.second});
    // 匿名函数替换cmp
    sort(v1.begin(), v1.end(), [](auto a, auto b) { return a.second > b.second; });
    sort(v2.begin(), v2.end(), [](auto a, auto b) { return a.second > b.second; });

    // 取出奇数位、偶数位出现次数最多的数字以及出现次数
    int id1 = v1[0].first, cnt1 = v1[0].second;
    int id2 = v2[0].first, cnt2 = v2[0].second;

    // 分类讨论 + 贪心
    int ans = 0;
    if (id1 != id2) {  // 奇数、偶数位置出现次数最多的数字不同
        ans = n - cnt1 - cnt2;
    } else {  // 奇数、偶数位置出现次数最多的数字相同
        if (v1.size() == 1 && v2.size() == 1)
            ans = n / 2;
        else if (v1.size() >= 2 && v2.size() >= 2) {  //
            ans = min(n - cnt1 - v2[1].second, n - cnt2 - v1[1].second);
        } else if (v1.size() >= 2 && v2.size() == 1) {
            ans = n - cnt2 - v1[1].second;
        } else if (v1.size() == 1 && v2.size() >= 2) {
            ans = n - cnt1 - v2[1].second;
        }
    }
    cout << ans << endl;

    return 0;
}