526互联

Codeforces Round 837 (Div. 2) A. Hossam and Combinatorics

发布时间 2023-09-05 21:25:57作者: zsxuan

给一个长为 \(n\) 的数组 \(a\) ，统计出所有二元组 \((a_i, a_j)\) 数量，满足以下条件：

  • \(1 \leq j < i \leq n, |a_i - a_j| = max_{1 \leq p,q \leq n} |a_{p} - a_{q}|\)

显然贡献不绑定位置，且考虑绝对值的情况，数组排序后去除绝对值。

此时即统计出 \((a_i, a_j)\) 数量，满足

  • \(1 \leq j < i \leq n, a_i - a_j = a_n - a_1\) 。

然后将这个数量乘以二即可，有序数组中选出的两个数可以在 \((a_i, a_j)\) 中任选一个位置。

取最左连续相同段 \(h\) ，最右连续相同段 \(w\) 。

  • 若 \(h = n\) ，所有数相等，从 \(n\) 中任选两个 \(2 \cdot \binom{n}{2} = n(n-1)\) 。
  • 若 \(h < n\) ，根据乘法原理答案为 \(2 \times h \cdot w\) 。

此题使用线性做法与排序做法差不多。

view 
#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n);
	for (int i = 0; i < n; i++) std::cin >> a[i];
	std::sort(a.begin(), a.end());
	int l = 0; while (l + 1 < n && a[l+1]==a[l]) l++;
	if (l == n - 1) {
		std::cout << 1LL * n * (n - 1) << '\n';
		return;
	}
	int r = n - 1; while (r - 1 >= 0 && a[r-1]==a[r]) --r;
	std::cout << 2LL * (l + 1) * (n - r) << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}