https://codeforces.com/contest/2063/problem/D
题目大意
给出 $n \ (\le 2 \times 10^5)$ 个点坐标为 $(a_i, 0)$ 以及 $m \ (\le 2 \times 10^5)$ 个点坐标为 $(b_i, 2)$。（$a_i, b_i$ 各自没有重复点）
问从这些点中选出非退化的三角形最多多少个（点不能重复选）。记最大数量为 $mx$，对于所有 $i \in [1, mx]$，问精确的选出 $i$ 个的最大面积和。
简要题解
首先我们可以直接靠枚举确定最大的组数。
观察：
- 非退化的三角形只能是 $a$ 中选两个点，$b$ 中选一个点，或者 $a$ 中选一个点，$b$ 中选两个点。
- 三角形的面积就是选两个点的那一边的边长（因为高总是 $2$）。
- 一个点的一边的选取对于面积没有影响。
- 如果在 $a$ 上选了 $k$ 对底，则总可以这样匹配，第一个匹配最后一个，第二个匹配倒数第二个。
- $k$ 对总是选最小的和最大的 $k$ 个点。
证明 4：对于两组点 $l_1, r_1, l_2, r_2$，不妨设 $l_1 < l_2$。此时有：
- $l_1 < l_2 < r_2 < r_1$ 即我们说的最好的情况
[ ]
[ ]
- $l_1 < l_2 < r_1 < r_2$ 我们交换 $r_1, r_2$ 变成情况 $1$ 答案是完全一致的。
[ ]
[ ]
[ ]
[ ]
- $l_1 < r_1 < l_2 < r_2$ 我们如下交换变成 $1$，能得到更好的结果。
[ ]
[ ]
[ ]
[ ]
证明 5: 显然如果左边的第 $i \ (\le k)$ 个没选，则把已经选了的 $l_i$ 换到这里更优（此时前 $i$ 个位置一定选了少于 $i$ 个则 $l_i$ 一定大于 $a_i$）。
有了这些，我们发现当我们求出了所有的对子之后，相当于一个二路归并。因为没有重复值，因此两个序列都是单调递减的。
但是我们很容易想到我们并不能总是这么贪下去，因为另一边实际上也会消耗要选的值。举例
1 2 3 4 5 6
1 2 3 18 19 20
显然我们能选出 $4$ 组，但是如果我们先把下面 3 组选了，就无法选出 $4$ 组了。此时我们需要将下面这组已经满了的情况退还一组，因为退还一组上面就可以选两组了。
没有任何一边先选满时，我们贪心的正确性是显然的。特别注意，相同元素优先选谁是无所谓的。 当有一边先选满时，将选满的这一边的某些舍弃，是必须的，而因为未选的都比它小，因此一定是只舍弃最小的一组，再选入另一侧没选的尽量大的两个。某相同的元素最多只有不同组之间的一对，此时如果选了将要顶满的，也会在下次操作退出来，变为选另一边，反之则没有退出这一步，不会影响答案。
复杂度
$T$：$O(n \log n + m \log m)$ （如果不需要排序的话，$O(n + m)$ 就好了）
$S$：$O(n + m)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, m; cin >> n >> m;
vector<int> a(n);
vector<int> b(m);
for (int& i : a) cin >> i;
for (int& i : b) cin >> i;
int mx = 0;
for (int i = 0; i * 2 <= n && i <= m; i++) {
cmax(mx, i + min(n - i * 2, (m - i) / 2));
}
cout << mx << '\n';
sort(a.begin(), a.end());
sort(b.begin(), b.end());
vector<int> sa;
vector<int> sb;
for (int l = 0, r = n - 1; l < r; l++, r--) {
sa.push_back(a[r] - a[l]);
}
for (int l = 0, r = m - 1; l < r; l++, r--) {
sb.push_back(b[r] - b[l]);
}
int i = 0, j = 0;
LL cur = 0;
for (int ii = 1; ii <= mx; ii++) {
int ln = (n - i * 2 - j), lm = (m - i - j * 2);
if (ln >= 2 && lm >= 2) {
if (sa[i] > sb[j]) {
cur += sa[i++];
} else {
cur += sb[j++];
}
} else if (ln < 2) {
if (ln == 1) {
cur += sb[j++];
} else {
cur -= sa[--i];
cur += sb[j++];
cur += sb[j++];
}
} else { // lm < 2
if (lm == 1) {
cur += sa[i++];
} else {
cur -= sb[--j];
cur += sa[i++];
cur += sa[i++];
}
}
cout << cur << (" \n"[ii == mx]);
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Remove Exactly Two - Codeforces Round 1000 (Div. 2)