Cats Transport 题解

问题分析

有n只猫，m个笼子。每只猫i有捕获时间t[i]，每个笼子j有关闭时间s[j]。若猫i在笼子j关闭前被捕获，需支付费用s[j]-t[i]，否则无需支付。目标是将n只猫分配到m个笼子，最小化总费用。

关键观察

1. 将猫的捕获时间t[i]排序：t[1] ≤ t[2] ≤ ... ≤ t[n]
2. 将笼子关闭时间s[j]排序：s[1] < s[2] < ... < s[m]
3. 每个笼子应放置t[i]尽可能大的猫，以最小化(s[j]-t[i])

动态规划状态定义

设dp[i][j]表示将前i只猫分配到j个笼子的最小费用。

转移方程

对第j个笼子，考虑分配前k只猫到前j-1个笼子，第j个笼子分配k+1到i只猫：
dp[i][j] = min_{0 ≤ k < i} [ dp[k][j-1] + sum_{t=k+1}^i (s[j]-t[t]) ]
其中sum_{k+1}^i (s[j]-t[t]) = s[j]*(i-k) - (sum_t[i]-sum_t[k])，sum_t[i]为前i只猫的t之和。

化简转移方程

dp[i][j] = min_{k} [ (dp[k][j-1] + sum_t[k] - s[j]·k) + s[j]·i - sum_t[i] ]
令a_k = -s[j]，b_k = dp[k][j-1] + sum_t[k]，则：
dp[i][j] = min(a_k·k + b_k) + (s[j]·i - sum_t[i])

##斜率优化与凸包维护 因s[j]递增，a_k = -s[j]递减可维护凸包。用单调队列存储候选k，通过斜率比较删除非优解。

代码实现

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

typedef long long ll;
const int MAXN = 1e5 + 5;
const ll INF = 1e18;

int n, m; ll t[MAXN], s[MAXN], sum_t[MAXN];
ll dp[2][MAXN]; // 滚动数组优化空间

// 计算两点(k1,b1)和(k2,b2)的斜率（交叉相乘避免精度问题）
bool isBad(int k1, int k2, int k3, ll b1, ll b2, ll b3) {
    return (k2 - k1) * (b3 - b2) >= (k3 - k2) * (b2 - b1);
}

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

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

    sort(t + 1, t + n + 1); sort(s + 1, s + m + 1);
    for (int i = 1; i <= n; i++) sum_t[i] = sum_t[i - 1] + t[i];

    // 初始化dp[0][0] = 0，其余为INF
    for (int i = 0; i <= n; i++) dp[0][i] = INF;
    dp[0][0] = 0;

    for (int j = 1; j <= m; j++) { // j个笼子
        int prev = (j - 1) % 2;
        int curr = j % 2;
        deque<int> dq; // 存储候选k

        for (int i = j; i <= n; i++) { // j个笼子至少放j只猫
            if (s[j] <= t[i]) continue; // 无法分配，跳过

            // 当前k = i-1，加入凸包
            int k = i - 1;
            ll b = dp[prev][k] + sum_t[k];
            while (dq.size() >= 2) {
                int k1 = dq[dq.size() - 2], k2 = dq.back();
                ll b1 = dp[prev][k1] + sum_t[k1], b2 = dp[prev][k2] + sum_t[k2];
                if (isBad(k1, k2, k, b1, b2, b)) dq.pop_back();
                else break;
            }
            dq.push_back(k);

            // 弹出队首非优解
            while (dq.size() >= 2) {
                int k1 = dq[0], k2 = dq[1];
                ll b1 = dp[prev][k1] + sum_t[k1], b2 = dp[prev][k2] + sum_t[k2];
                if (s[j] * (k2 - k1) >= (b2 - b1)) dq.pop_front();
                else break;
            }

            // 取最优k计算dp[curr][i]
            int best_k = dq.front();
            dp[curr][i] = dp[prev][best_k] + sum_t[best_k] - s[j] * best_k + s[j] * i - sum_t[i];
        }

        // 滚动数组更新
        for (int i = 0; i <= n; i++) dp[prev][i] = dp[curr][i];
    }

    cout << dp[m % 2][n] << endl;
    return EXIT_SUCCESS; // 注：原代码可能有笔误，此处修正为EXIT_SUCCESS
}

E55 斜率优化DP Cats Transport