[bzoj 4868] [Shoi2017]期末考试

n位同学, m门课程, 每门课程有成绩的公布时间bi (单位: 天), 设最晚的时间为last. 第i位同学等待成绩的代价为 max { 0, last - ti }. 两个操作: 1. 将课程X的时间推迟一天, 将课程Y的时间提前一天, 每次产生代价A. 2. 将课程Y的时间提前一天, 每次产生代价B.

X,Y可任意指定, 操作次数不限, 求最小总代价. (1≤n,m,ti,bi,≤10^5, 0≤A,B≤10^5, 存在几组数据, 使得C=10^18, 其余数据0≤C≤10^5) 也许我应该回到NOIP普及组......

只有 last 对等待成绩的代价有贡献. 枚举它. 如果B≤A, 显然可以只用操作2. 否则, 计算出 last 之前的课程总共可以推迟多少天, 优先使用操作1, 不够再用操作2.

C=10^18乘法会溢出. 由于最终的答案不会大于10^15, 只要C和一个正整数相乘, 该方案就不会是最优的.

通过前缀和, 对于每个 last, 可以 O(1) 计算出最小总代价.

typedef long long ll;

const int N = 1e5;

int t[N+1], b[N+1];

int main()
{
	ll A, B, C, t_cnt = 0, b_cnt = 0, b_sum = 0, b_tot = 0, t_sum = 0, ans = 1e15 + 10;
	int n, m;
	scanf("%lld%lld%lld%d%d", &A, &B, &C, &n, &m);
	rep (i, 0, n) {
		int x;
		scanf("%d", &x);
		++t[x];
	}
	rep (i, 0, m) {
		int x;
		scanf("%d", &x);
		++b[x];
		b_tot += x;
	}
	rep (i, 1, N+1) {
		t_cnt += t[i];
		t_sum += 1LL * t[i] * i;
		b_cnt += b[i];
		b_sum += 1LL * b[i] * i;

		ll w = t_cnt * i - t_sum;
		if (C >= 1e16 && w > 0) break;

		ll x = b_tot - b_sum - (m-b_cnt) * i, y = b_cnt * i - b_sum, z = min(x, y);
		ans = min(ans, z * min(A, B) + (x-z) * B + w * C);
	}
	printf("%lld\n", ans);
	return 0;
}

为什么没搞出来呢......一开始我还注意到只会等最后一门课程, 但是不知道从什么时候起, 又以为所有课程都会被等待......果然和我参加NOIP普及组时犯了一样的错误......TAT