自留题解

三分答案

因为 答案 受到 两个方程 的约束
所以 一定是 一条 抛物线--高中数学
那么 就需要 三分 找 拐点（是叫拐点把）

三分入门博客
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;
}