题意
给定长度为 \(n\) 的序列 \(t\) 和长度为 \(m\) 的序列 \(b\)，以及常数 \(A,B,C\)，可以进行两种操作：
- 选取任意 \(1 \le x,y \le n\)，并使 \(b_x + 1,b_y-1\)，记进行了 \(\alpha\) 次这种操作；
- 选取任意 \(1 \le z \le n\)，并使 \(b_z - 1\)，记进行了 \(\beta\) 次这种操作。
求进行若干次操作后，
\[\alpha \cdot A + \beta \cdot B + \sum_{i=1}^n \max\{0,- t_i + \max_{j=1}^m b_j\} \]的最小值。
sol
我们可以枚举 \(\max_{j=1}^m b_j\) 的值 \(tt\)，贪心地计算在这种情况下最小的 \(\alpha \cdot A + \beta \cdot B\)，具体地，设 \(sumbr=\sum_{i=1}^n \max\{0, b_i - tt\},sumbl=\sum_{i=1}^n \max\{0,- b_i + tt\}\)。 若 \(B\le A\)，则 \(\alpha=0\)，即结果为 \(sumbr \cdot B\)，否则，对 \(sumbl \ge sumbr\) 和 \(sumbl < sumbr\) 两种情况进行大力分讨，然后加上 \(\sum_{i=1}^n \max\{0,- t_i + tt\}\) 即可 ，推导仿照上例显然。
我们发现，我们需要计算一段的和，因此提前排序并预处理前缀和即可。
时间复杂度 \(O(n\log n)\)，理论可以优化到 \(O(n)\)，瓶颈就变成了前缀和了
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ULL;
const int N = 100005;
int n, m;
int t[N], b[N];
ULL st[N], sb[N];
int A, B;
ULL C;
int main(){
scanf("%d%d%lld", &A, &B, &C);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &t[i]);
for (int i = 1; i <= m; i ++ ) scanf("%d", &b[i]);
sort(t + 1, t + n + 1 ), sort(b + 1, b + m + 1);
for (int i = 1; i <= n; i ++ ) st[i] = st[i - 1] + t[i];
for (int i = 1; i <= m; i ++ ) sb[i] = sb[i - 1] + b[i];
int l = t[1], r = b[m];
__int128 ans = 1e35;
for (int time = l; time <= r; time ++ ) {
int bpr = upper_bound(b + 1, b + m + 1, time) - b;
int bpl = bpr - 1;
int mvp = upper_bound(t + 1, t + n + 1, time) - t - 1;
__int128 res = 0;
if (B <= A) res = ((sb[m] - sb[bpr - 1]) - (ULL) time * (m - bpr + 1)) * B;
else if ((sb[m] - sb[bpr - 1]) - (ULL) time * (m - bpr + 1) <= (ULL) time * bpl - sb[bpl]) res = ((sb[m] - sb[bpr - 1]) - (ULL) time * (m - bpr + 1)) * A;
else res = (__int128) ((ULL) time * bpl - sb[bpl]) * A + (__int128) (sb[m] - sb[bpr - 1] - (ULL) time * (m - bpr + 1) - ((ULL) time * bpl - sb[bpl])) * B;
res += (__int128) (-st[mvp] + (ULL) time * mvp) * C;
ans = min(ans, res);
}
> (ULL) ans);
return 0;
} printf("%llu\n", (ULL) ans);
return 0;
}