三分答案
因为 答案 受到 两个方程 的约束
所以 一定是 一条 抛物线--高中数学
那么 就需要 三分 找 拐点(是叫拐点把)
三分入门博客
https://blog.csdn.net/u012469987/article/details/50897291
(侵删)
#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define re register #define il inline #define inf INT_MAX #define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) const int maxn = 1e5 + 54; ll A, B, C; ll n, m; ll t[maxn], b[maxn]; ll chk(ll x) { ll res = 0; if (A < B) { ll rest = 0, need = 0; for (int i = 1; i <= m; i++) if (b[i] < x) rest += x - b[i]; for (int i = 1; i <= m; i++) if (b[i] > x) need += b[i] - x; if (rest >= need) res += need * A; else res += rest * A + (need - rest) * B; } else for (int i = 1; i <= m; i++) if (b[i] > x) res += (b[i] - x) * B; for (int i = 1; i <= n; i++) if (t[i] < x) res += (x - t[i]) * C; return res; } int main() { scanf("%lld%lld%lld", &A, &B, &C); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%lld", &t[i]); for (int i = 1; i <= m; i++) scanf("%lld", &b[i]); // 给的数据范围 有问题 // 实际上 C 很大 // 这不是bzoj原题吗?.jpg //简单贪心处理特殊情况 if (C == 1e16) { ll ans = 1e18; for (int i = 1; i <= n; i++) ans = min(ans, t[i]); printf("%lld\n", chk(ans)); return 0; } ll l = 1, r = 1e5; while (l + 2 < r) { ll mid1 = l + (r - l) / 3; ll mid2 = r - (r - l) / 3; ll val1 = chk(mid1); ll val2 = chk(mid2); if (val1 == val2) l = mid1, r = mid2; else if (val1 < val2) r = mid2; else l = mid1; } ll res1 = chk(l), res2 = chk(r), res3 = chk((2 * l + r) / 3), res4 = chk((2 * r + l) / 3); printf("%lld\n", min(min(res1, res2), min(res3, res4))); return 0; }