NC 20439 [SHOI2017] 三分

题意

传送门 NC 20439 [SHOI2017]期末考试

题解

不易直接求两种操作的次数，比较简单的解法是暴力枚举每一个最晚公布成绩的时间，更新答案。

观察函数也可以使用三分法。设最晚公布成绩的时间为 $T$，学生的不愉快度为 $f(x)$，操作一与操作二产生的不愉快度分别为 $g(x),w(x)$

$$f(T)=\sum _{T\ge t_i}(T-t_i)\times C$$ $$g(T)=\sum _{T\le b_i}(b_i-T)\times A$$ $$w(T)=\sum _{\sum _{T\le b_i}(b_i-T)\le \sum _{T\ge b_i}(T-b_i)}(b_i-T)\times B$$

$f(T)$ 的斜率为期望时间小于 $T$ 的学生数量的前缀和乘以 $C$，$g(T),w(T)$ 的斜率则是成绩公布时间大于 $T$ 的课程数量的后缀和分别乘以 $A,B$；可以观察到 $f(T)+g(T)+w(T)$ 只有相邻的驻点，单峰函数，三分求解即可。

#include <bits/stdc++.h> using namespace std; #define maxn 100005 typedef long long ll; ll A, B, C, n, m; ll tt[maxn], b[maxn]; inline void write(__int128 x) { if (!x) { putchar('0'); return; } char ch[40]; int cnt = 0; while (x) { ch[cnt++] = x % 10 + '0'; x /= 10; } while (cnt) { putchar(ch[--cnt]); } } __int128 judge(ll t) { __int128 res = 0, n1 = 0, n2 = 0; for (int i = 0; i < m; i++) { n1 += (b[i] < t ? (t - b[i]) : 0); n2 += (b[i] > t ? (b[i] - t) : 0); } if (B <= A) { res += n2 * B; } else { res += min(n1, n2) * A + (n2 > n1 ? (n2 - n1) * B : 0); } for (int i = 0; i < n; i++) { res += (tt[i] < t ? (__int128)(t - tt[i]) * C : 0); } return res; } int main() { scanf("%lld%lld%lld", &A, &B, &C); scanf("%lld%lld", &n, &m); for (int i = 0; i < n; i++) { scanf("%lld", tt + i); } ll maxt = 0; for (int i = 0; i < m; i++) { scanf("%lld", b + i); maxt = max(maxt, b[i]); } ll lb = 1, ub = maxt; while (ub - lb > 2) { ll m1 = (lb + ub) >> 1, m2 = (m1 + ub) >> 1; if (judge(m1) <= judge(m2)) ub = m2; else lb = m1; } __int128 res = -1; for (ll i = lb; i <= ub; i++) { __int128 tmp = judge(i); if (res == -1 || res > tmp) res = tmp; } write(res); putchar('\n'); return 0; }