题解 | P3745 [六省联考 2017] 期末考试

alt

题干分析

简要阐述一下题目要我们做什么:

n个学生都参加了m门考试.
每位学生对什么时候所有科目成绩均能出有一个预期.
如果某个同学在其预期时间内成绩未完全出,他每多等一天增加C点不愉快度.
现在学校为了减少总体学生的不愉快度,允许我们进行操作提前或延后某门课的出成绩时间.
我们可以使某些课程提前总共k天,同时使某些课程延后总共k天,这样做老师们会产生总计k * A点不愉快度
我们还可以只使某些课程提前总计k天,这样做会让老师们产生总计k * B点不愉快度
题目的核心便是找到一种调节方案,使老师和学生的总不愉快度最小.返回该总不愉快度

算法思路

我们可以预计到总不愉快随操作的变化是个单谷函数(或者单调函数):

我们不妨将所有未达到p要求天数前出成绩的科目通过操作全部达到p时间出成绩,当p=100000(不限制出成绩时间)时即为不进行操作,学生总不愉快度是最高的.
同样的,如果我们将p压缩到1,这时学生的总不愉快度一定为0(虽然听起来很扯就是了),老师的不愉快度此时达到最高.
我们的总值便是这两个对冲变量的和,因而是一个单谷函数(或者单调函数),因此我们使用三分法逼近最小的操作即可得到最小的总不愉快度.

实现代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m;
ll A,B,C,ans;
vector<int> t;
vector<int> b;

ll op(int p) { // 操作所引起的不愉快度(设定操作后所有科目最晚p天后必须出成绩)
    ll x = 0, y = 0; // x为允许推迟的总天数,y为需要提前的总天数
    for (int i = 1; i <= m; ++i) {
        if (b[i] < p) x += p - b[i];
        else y += b[i] - p;
    }
  	// 如果交换天数操作引起的不愉快度更低,我们更倾向于交换天数
  	// 天数不够(y比x大,即需要额外提前某些科目的出成绩时间),我们再强行提前这些科目的出成绩时间
    if (A < B) return min(x,y) * A + (y - min(x, y)) * B;
    return y * B; // 如果强行提前操作反而引起的不愉快度更小,我们直接全部强行提前就行了
}

ll total(int p) { // 最晚p天成绩全出,学生的总不愉快度
    ll sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (t[i] < p) sum += (p - t[i]) * C;
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> A >> B >> C;
    cin >> n >> m;

    t.resize(n + 1);
    b.resize(m + 1);

    for (int i = 1; i <= n; ++i) cin >> t[i];
    for (int i = 1; i <= m; ++i) cin >> b[i];

    sort(++t.begin(), t.end());
    sort(++b.begin(), b.end());

    if (C >= 1e16) { // 特判,C极大,我们直接让所有学生满足,苦一苦老师们
        cout << op(t[1]);
        return 0;
    }

    ans = 1e16;
    int left = 1, right = 1e5;
    while (right - left > 2) {
        int mid1 = left + (right - left) / 3, mid2 = right - (right - left) / 3;
        ll c1 = op(mid1) + total(mid1);
        ll c2 = op(mid2) + total(mid2);
        if (c1 <= c2) right = mid2;
        else left = mid1;
    }

    for (int i = left; i <= right; ++i) {
        ll x = op(i) + total(i);
        ans = min(ans, x);
    }
    cout << ans;

    return 0;
}