Codeforces Round 837 (Div. 2) A. Hossam and Combinatorics
给一个长为 \(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;
}