p3745

问题分析

题目要求我们通过调整课程成绩公布时间，使得总的不愉快度最小。不愉快度由两部分组成：

1. 学生等待的不愉快度：如果学生 希望在第 天或之前得知成绩，但最后公布成绩的课程在第 天（）公布，则该学生每天产生 的不愉快度，总不愉快度为 。
2. 调整操作的不愉快度：有两种操作：
   • 操作1：将课程 的部分老师调整到课程 ，使 推迟一天、 提前一天，每次操作产生 的不愉快度。
   • 操作2：增加老师使课程 提前一天，每次操作产生 的不愉快度。

目标是将所有课程的成绩公布时间调整至不超过某一天 ，并最小化总不愉快度（操作代价 + 学生等待代价）。

关键思路

• 最后公布日 ：所有课程必须在 天或之前公布成绩。 的选择是核心，它平衡了调整操作的代价（ 越小，调整代价越大）和学生等待的代价（ 越大，等待代价越大）。
• 调整代价计算：
  • need：所有原公布时间 的课程需要提前的总天数，即 。
  • extra：所有原公布时间 的课程可推迟的总天数（用于操作1转移），即 。
  • 最小操作代价：
    • 可转移的天数为 ，每的代价为 （因为操作1代价 和操作2代价 中取较小者）。
    • 剩余需提前的天数为 ，只能用操作2，代价为 每的。
    • 总调整代价 = 。
• 学生等待代价：所有 的学生，总等待代价为 。
• 候选 的选择：最优 一定出现在关键点附近，即每个 和 的邻域（ 和 ），以及边界值（如1和足够大的上界）。这是因为调整代价和等待代价在这些点处变化最剧烈。

算法步骤

1. 输入处理：读取 ，学生数 ，课程数 ，学生期望时间数组 ，课程原公布时间数组 。
2. 预处理：
   • 对 和 排序。
   • 计算前缀和数组 prefix_t 和 prefix_b，用于快速计算区间和。
3. 生成候选 ：
   • 收集所有 和 （确保 ）。
   • 添加边界值1和足够大的上界（如 ）。
   • 去重并排序候选 。
4. 枚举候选 ：
   • 计算 need：
     • 二分查找 中第一个大于 的位置 。
     • 。
     • 。
     • 。
   • 计算 extra：
     • 。
     • 。
     • 。
   • 计算等待代价：
     • 二分查找 中第一个不小于 的位置 （即 的学生数）。
     • 。
     • 。
   • 计算总代价：
     • 。
     • 。
   • 更新最小总代价。
5. 输出结果：最小总代价。

复杂度分析

• 排序：。
• 前缀和：。
• 候选 生成：最多 个候选点。
• 每个候选 的处理：两次二分查找 。
• 总复杂度：，可处理 的数据。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <climits>
using namespace std;
typedef long long ll;

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

    ll A, B, C;
    cin >> A >> B >> C;
    ll n, m;
    cin >> n >> m;
    vector<ll> t_vec(n), b_vec(m);
    for (int i = 0; i < n; i++) {
        cin >> t_vec[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b_vec[i];
    }

    sort(t_vec.begin(), t_vec.end());
    sort(b_vec.begin(), b_vec.end());

    vector<ll> prefix_t(n + 1, 0), prefix_b(m + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix_t[i + 1] = prefix_t[i] + t_vec[i];
    }
    for (int i = 0; i < m; i++) {
        prefix_b[i + 1] = prefix_b[i] + b_vec[i];
    }

    ll total_sum_b = prefix_b[m];

    set<ll> candidate_M;
    candidate_M.insert(1);
    ll global_max = 1;
    if (m > 0) {
        global_max = max(global_max, b_vec.back());
        for (ll x : b_vec) {
            if (x - 1 >= 1) candidate_M.insert(x - 1);
            candidate_M.insert(x);
            candidate_M.insert(x + 1);
        }
    }
    if (n > 0) {
        global_max = max(global_max, t_vec.back());
        for (ll x : t_vec) {
            if (x - 1 >= 1) candidate_M.insert(x - 1);
            candidate_M.insert(x);
            candidate_M.insert(x + 1);
        }
    }
    ll max_candidate = global_max + 100000;
    candidate_M.insert(max_candidate);

    vector<ll> M_vec;
    for (ll M : candidate_M) {
        if (M >= 1 && M <= max_candidate) {
            M_vec.push_back(M);
        }
    }
    sort(M_vec.begin(), M_vec.end());

    ll ans = (ll)1e18;

    for (ll M : M_vec) {
        ll need = 0;
        ll extra = 0;
        if (m > 0) {
            auto it_b = upper_bound(b_vec.begin(), b_vec.end(), M);
            int idx_b = it_b - b_vec.begin();
            ll count_need = m - idx_b;
            ll sum_need = total_sum_b - prefix_b[idx_b];
            need = sum_need - M * count_need;

            ll count_extra = idx_b;
            ll sum_extra = prefix_b[idx_b];
            extra = M * count_extra - sum_extra;
        }

        ll waiting = 0;
        if (n > 0) {
            auto it_t = lower_bou***ec.begin(), t_vec.end(), M);
            int idx_t = it_t - t_vec.begin();
            ll sum_t = prefix_t[idx_t];
            waiting = C * (M * idx_t - sum_t);
        }

        ll transfer = min(need, extra);
        ll cost_op = transfer * min(A, B) + max(0LL, need - extra) * B;
        ll total_cost = cost_op + waiting;
        if (total_cost < ans) {
            ans = total_cost;
        }
    }

    cout << ans << endl;
    return 0;
}

关键点解析

1. 输入与预处理：读取数据后，对学生的期望时间 和课程的原公布时间 排序，并计算前缀和数组，以便快速计算区间和。
2. 候选 生成：收集所有关键点（ 和 邻域）及边界值，去重后排序。
3. 枚举候选 ：
   • need 计算：使用二分查找定位大于 的课程，计算需要提前的总天数。
   • extra 计算：计算可推迟的总天数（用于操作1）。
   • 等待代价：使用二分查找定位期望时间小于 的学生，计算总等待代价。
   • 调整代价：结合 和 计算最小操作代价。