题意两条线上分别有n, m个点， 两条线之间的距离为2。
有操作f : 取得一条线上选2个点， 另一条线上选1个点所围成的三角形的面积。
记最多能操作k次
输出：
两行
第一行 k
第二行 k个整数 第i个表示 操作i次取得的面积总和的最大值
反悔贪
如果两边都能取， 取最大
有一边点的数量为0时， 而另一边至少有3个点, 如果能回退就回退
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(m + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
}
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
vector<int> d1, d2;
d1.push_back(0), d2.push_back(0);
for (int l = 1, r = n; l < r; l++, r--) {
d1.push_back(a[r] - a[l]);
}
for (int l = 1, r = m; l < r; l++, r--) {
d2.push_back(b[r] - b[l]);
}
int len1 = n, len2 = m;
vector<ll> ans;
int i = 1, j = 1;
int tmp = 0;
while (len1 || len2) {
if (len1 == 0 || len2 == 0) {
if (len1 == 0) {
if (i == 1 || len2 < 3) break;
tmp -= d1[--i];
tmp += d2[j++];
tmp += d2[j++];
len2 -= 3;
} else {
if (j == 1 || len1 < 3) break;
tmp -= d2[--j];
tmp += d1[i++];
tmp += d1[i++];
len1 -= 3;
}
ans.push_back(tmp);
continue;
}
auto check = [&](int num) {
if (num == 1) {
tmp += d1[i];
i++;
len1 -= 2;
len2--;
} else {
tmp += d2[j];
j++;
len1--;
len2 -= 2;
}
ans.push_back(tmp);
};
if (len1 >= 2 && len2 >= 2) {
if (d1[i] > d2[j]) {
check(1);
} else {
check(2);
}
} else if (len1 >= 2 && len2 >= 1) {
check(1);
} else if (len1 >= 1 && len2 >= 2) {
check(2);
} else {
break;
}
}
cout << ans.size() << "\n";
for (auto k : ans) {
cout << k << " ";
}
cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}