Codeforces Round 967 (Div. 2)

Lazy_boy_2024-09-022025-03-31

A.Make All Equal

题目描述

You are given a cyclic array $a_1,a_2,…,a_n$ .
You can perform the following operation on a at most $n−1$ times:

Let m be the current size of a, you can choose any two adjacent elements where the previous one is no greater than the latter one (In particular, $a_m$ and $a_1$ are adjacent and $a_m$ is the previous one), and delete exactly one of them. In other words, choose an integer i ( $1 \le i \le m$ ) where $a_i \le a_{(i \mod m)+1}$ holds, and delete exactly one of $a_i$ or $a_{(i \mod m) + 1}$ from aa.
Your goal is to find the minimum number of operations needed to make all elements in aa equal.

题目意思是想让我们用最少的操作次数删除数组中的元素获得数组中的数字全相等的数组。

解题思路

由于需要最小的操作数，我们可以直接剩下数目最多的数字，于是就可以使用 STL 中的 map 完成此题

参考代码

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve() {
  int n;
  std::cin >> n;
  std::map<int, int> mp;
  for(int i = 0, x; i < n; i++) {
    std::cin >> x;
    mp[x]++;
  }

  int res = 0;
  for(auto [x, y] : mp) {
    res = std::max(res, y);
  }
  std::cout << n - res << endl;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr), std::cout.tie(nullptr);
  int Lazy_boy_ = 1;
  std::cin >> Lazy_boy_;
  while (Lazy_boy_--) solve();
  return 0;
}