题解：Codeforces Round 967 (Div. 2) A [暴力/贪心]

本文主要是介绍题解：Codeforces Round 967 (Div. 2) A [暴力/贪心]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Make All Equal

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given a cyclic array $a_1,a_2,\dots ,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\mathrm{mod}m)+1}$ holds, and delete exactly one of $a_i$ or $a_{(i\mathrm{mod}m)+1}$ from $a$.

Your goal is to find the minimum number of operations needed to make all elements in $a$ equal.

给你一个循环数组 $a_1,a_2,\dots ,a_n$ 。

你最多可以对 $a$ 执行 $n-1$ 次以下操作：

• 假设 $m$ 是 $a$ 的当前大小，你可以选择任意两个相邻的元素，其中前一个元素不大于后一个元素（特别是 $a_m$ 和 $a_1$ 是相邻的，而 $a_m$ 是前一个元素），并恰好删除其中一个元素。换句话说，选择一个 $a_i\le a_{(i\mathrm{mod}m)+1}$ 成立的整数 $i$ （ $1\le i\le m$ ），并从 $a$ 中恰好删除 $a_i$ 或 $a_{(i\mathrm{mod}m)+1}$ 中的一个。

你的目标是找出使 $a$ 中所有元素相等所需的最少运算次数。

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 500$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 100$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$) — the elements of array $a$.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1\le t\le 500$ )。测试用例说明如下。

每个测试用例的第一行包含一个整数 $n$ ( $1\le n\le 100$ ) - 数组的长度 $a$ 。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le n$ ) - 数组 $a$ 的元素。

Output

For each test case, output a single line containing an integer: the minimum number of operations needed to make all elements in $a$ equal.

输出

对于每个测试用例，输出一行包含一个整数：使 $a$ 中所有元素相等所需的最少操作数。

Example

Input

7
1
1
3
1 2 3
3
1 2 2
5
5 4 3 2 1
6
1 1 2 2 3 3
8
8 7 6 3 8 7 6 3
6
1 1 4 5 1 4

Output

0
2
1
4
4
6
3

Note

In the first test case, there is only one element in $a$, so we can’t do any operation.

In the second test case, we can perform the following operations to make all elements in $a$ equal:

• choose $i=2$, delete $a_3$, then $a$ would become $[1,2]$.
• choose $i=1$, delete $a_1$, then $a$ would become $[2]$.

It can be proven that we can’t make all elements in $a$ equal using fewer than $2$ operations, so the answer is $2$.

注

在第一个测试用例中， $a$ 中只有一个元素，因此我们无法进行任何操作。

在第二个测试用例中，我们可以执行以下操作，使 $a$ 中的所有元素相等：

• 选择 $i=2$ ，删除 $a_3$ ，那么 $a$ 将变为 $[1,2]$ 。
• 选择 $i=1$ ，删除 $a_1$ ，则 $a$ 将变为 $[2]$ 。

可以证明，使用少于 $2$ 的运算无法使 $a$ 中的所有元素相等，因此答案是 $2$ 。

题意

有一个循环数组 $a$
你每次可以操作：

对数组中相邻两个不同的数字删去任意一个（首尾两个也算相邻）
你需要不断操作，直到数组中只有一种元素时停止
问：你至少需要操作多少次

题解

只需要用一个map存储某种数字出现的个数
然后最后的数组就是全部那种数字了
所以只需要输出
$$数组总数-出现最多数字的个数$$
即可

代码

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
#define all(x) x.begin(),x.end()using i64 = long long;
const int N = 2e5 + 10;
int t = 1;
int a[N];void solve() {std::map<int,int> mp;int n;std::cin >> n;int max = 0;for(int i = 0 ; i < n ; i ++) {int num;std::cin >> num;mp[num]++;max = std::max(max,mp[num]);}std::cout << n - max << "\n";
}signed main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cin >> t;while(t--){solve();}return 0;
}

有什么建议或者意见的欢迎在评论区留言！

转载自博客https://www.cnblogs.com/jiejiejiang2004/p/18371667
博主已同意，我就是博主

这篇关于题解：Codeforces Round 967 (Div. 2) A [暴力/贪心]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---