[蓝桥杯 2024 省 A] 训练士兵的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求计算使所有士兵达到所需训练次数的最小总花费：每次组团训练为全体士兵各增加一次训练并花费 $S$ ~S~ 金币，也可以单独为某名士兵训练（每次 $p_i$ ~p_i~ 金币）。核心解法是枚举组团训练次数 $k$ ~k~，用排序与后缀和快速计算每种 $k$ ~k~ 下的花费并取最小值。

分析

核心观察

若购买 $k$ ~k~ 次组团训练，士兵 $i$ ~i~ 还差 $\max(0, c_i - k)$ ~\max(0, c_i - k)~ 次训练需单独完成，总花费为 $kS + \sum_i \max(0, c_i - k) p_i$ ~kS + \sum_i \max(0, c_i - k) p_i~；只需枚举 $k \in [0, \max c_i]$ ~k \in [0, \max c_i]~，因为超过最大需求后每多一次组团只会增加 $S$ ~S~ 而无任何节省。

思路

对固定的 $k$ ~k~：

$\displaystyle cost(k) = kS + \sum_{c_i > k} (c_i - k) p_i = kS + \sum_{c_i > k} c_i p_i - k \sum_{c_i > k} p_i$

按 $c_i$ ~c_i~ 升序排序士兵，预处理后缀和 $\rm{suf\_cp}[i] = \sum_{j \ge i} c_j p_j$ 与 $\rm{suf\_p}[i] = \sum_{j \ge i} p_j$ ~\rm{suf\_p}[i] = \sum_{j \ge i} p_j~。枚举 $k$ ~k~ 时，用指针找到第一个满足 $c_i > k$ ~c_i > k~ 的下标 $i_0$ ~i_0~（该下标之前士兵已不再需要单独训练），则：

$\displaystyle cost(k) = kS + \rm{suf\_cp}[i_0] - k \cdot \rm{suf\_p}[i_0]$

取所有 $k$ ~k~ 中的最小值即为答案。直观理解：多买一次组团的花费是 $S$ ~S~，节省的是当前仍需单独训练的士兵的 $p_i$ ~p_i~ 之和，最优 $k$ ~k~ 位于两者平衡处。

具体示例

以样例为例： $n = 3$ ~n = 3~， $S = 6$ ~S = 6~，士兵 $(p, c)$ ~(p, c)~ 为 $(5, 2)$ ~(5, 2)~、 $(2, 4)$ ~(2, 4)~、 $(3, 2)$ ~(3, 2)~。按 $c$ ~c~ 排序后为 $2, 2, 4$ ~2, 2, 4~，后缀和 $\rm{suf\_cp} = [24, 14, 8]$ ~\rm{suf\_cp} = [24, 14, 8]~、 $\rm{suf\_p} = [10, 5, 2]$ ~\rm{suf\_p} = [10, 5, 2]~。枚举： $k = 0$ ~k = 0~ 时花费 $24$ ~24~； $k = 1$ ~k = 1~ 时 $6 + 24 - 10 = 20$ ~6 + 24 - 10 = 20~； $k = 2$ ~k = 2~ 时 $12 + 8 - 4 = 16$ ~12 + 8 - 4 = 16~； $k = 3$ ~k = 3~ 时 $18 + 8 - 6 = 20$ ~18 + 8 - 6 = 20~； $k = 4$ ~k = 4~ 时 $24$ ~24~。最小花费为 $16$ ~16~，与样例一致。

算法步骤

读入 n、S 以及所有 (p_i, c_i)，记录最大需求 maxC。
将士兵按 c 升序排序。
预处理后缀和数组 suf_cp、suf_p。
枚举 k 从 $0$ ~0~ 到 maxC，用指针 ptr 维护第一个满足 $c > k$ ~c > k~ 的下标，计算花费 cost 为 $k \times S + \rm{suf\_cp}[ptr] - k \times \rm{suf\_p}[ptr]$ ，并更新最小值。
输出最小花费。

复杂度分析

时间： $O(n \log n + \max c_i)$ ~O(n \log n + \max c_i)~

空间： $O(n)$ ~O(n)~

实现注意事项

花费可能很大： $kS \le 10^{10} \times 10^6 = 10^{16}$ ~kS \le 10^{10} \times 10^6 = 10^{16}~， $\sum c_i p_i \le 10^{17}$ ~\sum c_i p_i \le 10^{17}~，需使用 64 位整数（long long）。
$k$ ~k~ 只需枚举到最大需求 $\max c_i$ ~\max c_i~，超过后每多一次组团只会增加 $S$ ~S~ 而无节省。
指针 ptr 随 $k$ ~k~ 单调右移，总移动次数为 $n$ ~n~，故枚举部分整体为 $O(\max c_i + n)$ ~O(\max c_i + n)~。
本题 $c_i \le 10^6$ ~c_i \le 10^6~，枚举全部 $k$ ~k~ 可行；若 $c_i$ ~c_i~ 更大，可利用花费函数的分段线性性质，只检查断点 $k = c_i$ ~k = c_i~ 与 $k = c_i - 1$ ~k = c_i - 1~ 附近的候选值。

源代码

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

int main() {
    int n;
    long long S;
    cin >> n >> S;

    vector<pair<long long, long long>> a(n);
    long long maxC = 0;
    for (int i = 0; i < n; i++) {
        long long p, c;
        cin >> p >> c;
        a[i] = {c, p};
        maxC = max(maxC, c);
    }
    sort(a.begin(), a.end());

    vector<long long> suf_cp(n + 1, 0), suf_p(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        suf_cp[i] = suf_cp[i + 1] + a[i].first * a[i].second;
        suf_p[i] = suf_p[i + 1] + a[i].second;
    }

    long long ans = LLONG_MAX;
    int ptr = 0;
    for (long long k = 0; k <= maxC; k++) {
        while (ptr < n && a[ptr].first <= k) ptr++;
        long long cost = k * S + suf_cp[ptr] - k * suf_p[ptr];
        ans = min(ans, cost);
    }
    cout << ans << '\n';
    return 0;
}

n, S = map(int, input().split())
soldiers = []
for _ in range(n):
    p, c = map(int, input().split())
    soldiers.append((c, p))
soldiers.sort()

m = n
suf_cp = [0] * (m + 1)
suf_p = [0] * (m + 1)
for i in range(m - 1, -1, -1):
    c, p = soldiers[i]
    suf_cp[i] = suf_cp[i + 1] + c * p
    suf_p[i] = suf_p[i + 1] + p

maxC = soldiers[-1][0]
ans = float("inf")
ptr = 0
for k in range(maxC + 1):
    while ptr < m and soldiers[ptr][0] <= k:
        ptr += 1
    cost = k * S + suf_cp[ptr] - k * suf_p[ptr]
    ans = min(ans, cost)
print(ans)

目前没有评论。