CF2232A题解

传送门：https://www.luogu.com.cn/problem/CF2232A

题意：给定一个序列，每次可以选择两个数将两者替换成两者之间任意的数。

首先将序列排序，肯定把所有数变成原序列中的某个数更优，否则可以把这个数替换成原序列中最近的那个数。

我们枚举替换成的那个数，把序列分成三段。分别小于，等于，大于枚举的数。

我们发现对于一段中间一段可以不进行操作，左右两段可以相互抵消，多出来的与中间一段消除。答案即为左右两段中较大一段的大小。

#include <bits/stdc++.h>using namespace std;int a[101];void solve() {int n;cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];sort(a + 1, a + n + 1);int ans = 0x3f3f3f3f;int l = 1;while (l <= n) {int r = l;while (r < n && a[r + 1] == a[l]) ++r;ans = min(ans, max(l - 1, n - r));l = r + 1;}cout << ans << '\n';
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}