luogu-P12733 磨合

GESP C++ 五级练习题，二分查找和贪心思想考点应用，五级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P12733 磨合

题目要求

题目背景

「能够像这样『磨合』，实在是帮了个大忙。」
——绫濑沙季

题目描述

悠太和沙季遇到了 $n$ 个问题，问题的难度分别为 $d_1,\dots,d_n$ 。
他们可以以任意顺序解决问题，对于准备解决的第 $i$ 个问题，每将难度减少 $1$ ，两人需要花费 $i$ 秒。将难度减少为 $0$ 时问题被解决，他们才可以继续解决下一个问题。
如果他们正在解决第 $i$ 个问题（即难度尚未减少为 $0$ ），但剩余时间少于 $i$ 秒，他们就不能继续解决剩下的问题了，第 $i$ 个问题也没有解决。
他们想要知道，如果共有 $t$ 秒，那么最多能解决多少个问题。由于他们可能面对很多种不同情况，所以会多次改变 $t$ 进行询问。

输入格式

第一行输入两个整数 $n,q$ 表示问题总数和询问次数。
第二行输入 $n$ 个整数，表示 $d_1,\dots,d_n$ 。
接下来 $q$ 行，每行输入一个整数表示询问的总时间 $t$ 。

输出格式

对于每次询问输出一行一个整数表示最多能解决的问题数量。

输入输出样例 #1

输入 #1

输出 #1

2
3

输入输出样例 #2

输入 #2

10 3
923 243 389 974 100 485 296 377 61 552
2403
5819
0

输出 #2

5
6
0

说明/提示

样例 1 解释

若 $t=10$ ，则第 $1$ 个解决难度为 $7$ 的问题，第 $2$ 个解决难度为 $1$ 的问题，花费的时间为 $1\times7+2\times1=9$ 秒。可以证明他们无法解决三个问题。

若 $t=16$ ，则依次解决难度为 $7,3,1$ 的问题，花费的时间为 $1\times7+2\times3+3\times1=16$ 秒。

数据范围与限制

本题采用捆绑测试，各 Subtask 的限制与分值如下。

Subtask No.	$n\le$	$q\le$	$d_i\le$	$t\le$	分值	依赖子任务
$1$	$10$	$1$	$10$	$10^3$	$13$
$2$	$10^3$	$1$	$10^3$	$10^9$	$24$	$1$
$3$	$10^3$	$10^6$	$10^3$	$10^9$	$16$	$1,2$
$4$	$10^6$	$1$	$10^3$	$10^{16}$	$16$	$1,2$
$5$	$10^6$	$10^6$	$10^3$	$10^{16}$	$31$	$1,2,3,4$

对于所有数据，满足 $1\le n,q\le10^6$ ， $1\le d_i\le10^3$ ， $0\le t\le10^{16}$ 。

题目分析

1. 贪心策略与数学推导

题目要求在有限时间 $t$ 内解决最多的问题。为了解决更多的问题，直观的想法是我们应该优先选择难度较小的问题（贪心策略 1）。

假设我们要解决 $k$ 个问题，根据题意，这 $k$ 个问题的解决顺序会影响总花费时间。设选出的 $k$ 个问题的难度从小到大排序为 $d'_1, d'_2, \dots, d'_k$ 。如果我们把这 $k$ 个问题按照某种顺序解决，第 $i$ 个解决的问题会被乘以系数 $i$ 。根据排序不等式（或者生活经验），为了使总和最小，我们应该让 较小的难度乘以较大的系数，较大的难度乘以较小的系数（贪心策略 2）。

即：

第 1 个解决的问题（系数 1）应该是这 $k$ 个里难度最大的 $d'_k$ 。
第 2 个解决的问题（系数 2）应该是难度第二大的 $d'_{k-1}$ 。
…
第 $k$ 个解决的问题（系数 $k$ ）应该是难度最小的 $d'_1$ 。

总花费公式为：

\text{Cost}(k) = 1 \cdot d'_k + 2 \cdot d'_{k-1} + \dots + k \cdot d'_1

2. 前缀和优化

我们发现上面的公式可以转化为前缀和的形式。设 $sum[i]$ 表示排序后前 $i$ 个难度之和，即 $sum[i] = d'_1 + d'_2 + \dots + d'_i$ 。再设 $cost[i]$ 为 $sum$ 的前缀和，即 $cost[i] = sum[1] + sum[2] + \dots + sum[i]$ 。

展开 $cost[k]$ ：

\begin{aligned} cost[k] &= sum[1] + sum[2] + \dots + sum[k] \\ &= (d'_1) + (d'_1 + d'_2) + \dots + (d'_1 + d'_2 + \dots + d'_k) \end{aligned}

在上述式子中：

$d'_1$ 出现了 $k$ 次（在 $sum[1] \dots sum[k]$ 中都有），总贡献 $k \cdot d'_1$ 。
$d'_2$ 出现了 $k-1$ 次（在 $sum[2] \dots sum[k]$ 中都有），总贡献 $(k-1) \cdot d'_2$ 。
…
$d'_k$ 出现了 $1$ 次（在 $sum[k]$ 中），总贡献 $1 \cdot d'_k$ 。

这正好对应了解决前 $k$ 个最小难度问题的最优总时间。因此，我们可以通过对原数组排序，并进行两次前缀和预处理，在 $O(1)$ 时间内求出解决任意 $k$ 个最小难度问题的最优时间 $cost[k]$ 。

3. 重点提示：TLE 问题与二分查找

本题的数据范围是 $N, Q \le 10^6$ 。这是一个非常大的数据规模。

为什么暴力会 TLE？ 对于每个询问 $t$ ，如果我们从 $k=1$ 开始遍历直到 $cost[k] > t$ ，单次查询的最坏时间复杂度是 $O(N)$ 。总时间复杂度为 $O(Q \times N) = 10^6 \times 10^6 = 10^{12}$ 。计算机每秒通常能处理 $10^8$ 级别运算， $10^{12}$ 远超 1 秒的时限，必然导致 Time Limit Exceeded (TLE)。
如何通过二分查找优化？ 我们发现 $cost[k]$ 是随着 $k$ 增大而单调递增的（因为难度 $d_i > 0$ ），这就满足了二分查找的单调性条件。因此，对于给定的 $t$ ，我们可以使用 二分查找 在 $cost$ 数组中快速找到第一个大于 $t$ 的位置，或者最后一个小于等于 $t$ 的位置。二分查找的复杂度是 $O(\log N)$ 。总时间复杂度优化为 $O(N \log N \text{ (排序)} + Q \log N \text{ (查询)})$ 。代入数据： $10^6 \times 20 \approx 2 \times 10^7$ ，完全可以在 1 秒内运行完成。
I/O 优化 由于输入输出量巨大（百万级），建议使用 std::ios::sync_with_stdio(false); std::cin.tie(NULL); 来加速 I/O，否则即使算法正确也可能因为读写太慢而 TLE。

4. 总结

排序：将难度从小到大排序。
预处理：计算两次前缀和得到 $cost$ 数组。
查询：对于每个 $t$ ，使用 upper_bound 或手写二分查找 cost 数组中满足 $\le t$ 的最大下标。

示例代码

方法一、手写二分查找

#include <algorithm>
#include <iostream>
#include <vector>

// 使用 long long 防止溢出，t 最大可达 10^16，累加和也会很大
typedef long long ll;

const int MAXN = 1000005;
ll d[MAXN];     // 存储问题难度
ll sum[MAXN];   // 难度的前缀和
ll cost[MAXN];  // 解决前 i 个问题的最小花费（即 sum 的前缀和）

int main() {
    // 优化 I/O 操作速度 (防止 TLE)
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, q;
    std::cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        std::cin >> d[i];
    }

    // 核心逻辑 1: 贪心
    // 为了让解决 k 个问题的总时间最少，我们应该：
    // 1. 选择难度最小的 k 个问题。
    // 2.
    // 在解决这k个问题时，把难度大的放在前面解决（乘数小），难度小的放在后面解决（乘数大）。
    //    具体推导：假设选了 k 个问题，难度从小到大排序为 a1, a2, ..., ak。
    //    第 1 个解决的问题耗时：1 * 难度
    //    第 i 个解决的问题耗时：i * 难度
    //    根据排序不等式，要使乘积之和最小，应该由小的系数乘大的难度，大的系数乘小的难度。
    //    即：1 * ak + 2 * ak-1 + ... + k * a1。
    //    这个式子等价于前缀和的前缀和。
    std::sort(d + 1, d + 1 + n);

    // 核心逻辑 2: 前缀和预处理
    // sum[i] = d[1] + ... + d[i]
    // cost[i] = sum[1] + ... + sum[i]
    //         = (d[1]) + (d[1]+d[2]) + ... + (d[1]+...+d[i])
    //         = i*d[1] + (i-1)*d[2] + ... + 1*d[i]
    // 这正好对应了解决前 i 个最小难度问题的最优总时间。
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + d[i];
        cost[i] = cost[i - 1] + sum[i];
    }

    // 处理询问
    for (int i = 0; i < q; i++) {
        ll t;
        std::cin >> t;

        // 核心逻辑 3: 二分查找 (手动实现)
        // 目标：找到满足 cost[x] <= t 的最大的 x
        // l: 可能解区间的左边界，r: 可能解区间的右边界，ans:
        // 记录当前找到的合法解
        ll l = 1, r = n, ans = 0;
        while (l <= r) {
            ll mid = l + (r - l) / 2;  // 防止 (l+r) 溢出
            if (cost[mid] <= t) {
                // 如果前 mid 个题也能做完，说明 mid 是一个可行解
                ans = mid;    // 记录这个可行解
                l = mid + 1;  // 尝试找更大的解，往右边搜
            } else {
                // 如果前 mid 个题做不完，说明 mid 太大了，答案肯定在左边
                r = mid - 1;
            }
        }
        std::cout << ans << "\n";
    }

    return 0;
}

方法二、利用upper_bound函数

#include <algorithm>
#include <iostream>
#include <vector>

// 使用 long long 防止溢出，t 最大可达 10^16，累加和也会很大
typedef long long ll;

const int MAXN = 1000005;
ll d[MAXN];     // 存储问题难度
ll sum[MAXN];   // 难度的前缀和
ll cost[MAXN];  // 解决前 i 个问题的最小花费（即 sum 的前缀和）

int main() {
    // 优化 I/O 操作速度 (防止 TLE)
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, q;
    std::cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        std::cin >> d[i];
    }

    // 核心逻辑 1: 贪心
    // 为了让解决 k 个问题的总时间最少，我们应该：
    // 1. 选择难度最小的 k 个问题。
    // 2.
    // 在解决这k个问题时，把难度大的放在前面解决（乘数小），难度小的放在后面解决（乘数大）。
    //    具体推导：假设选了 k 个问题，难度从小到大排序为 a1, a2, ..., ak。
    //    第 1 个解决的问题耗时：1 * 难度
    //    第 i 个解决的问题耗时：i * 难度
    //    根据排序不等式，要使乘积之和最小，应该由小的系数乘大的难度，大的系数乘小的难度。
    //    即：1 * ak + 2 * ak-1 + ... + k * a1。
    //    这个式子等价于前缀和的前缀和。
    std::sort(d + 1, d + 1 + n);

    // 核心逻辑 2: 前缀和预处理
    // sum[i] = d[1] + ... + d[i]
    // cost[i] = sum[1] + ... + sum[i]
    //         = (d[1]) + (d[1]+d[2]) + ... + (d[1]+...+d[i])
    //         = i*d[1] + (i-1)*d[2] + ... + 1*d[i]
    // 这正好对应了解决前 i 个最小难度问题的最优总时间。
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + d[i];
        cost[i] = cost[i - 1] + sum[i];
    }

    // 处理询问
    for (int i = 0; i < q; i++) {
        ll t;
        std::cin >> t;

        // 核心逻辑 3: 二分查找
        // 说明：std::upper_bound 在有序区间 [first, last) 中查找第一个 *大于* t
        // 的元素位置。 返回值是一个指针（或迭代器）。 假设 cost[k] <= t 且
        // cost[k+1] > t，那么 upper_bound 会返回 &cost[k+1]。
        // 我们计算下标偏移量： ans = &cost[k+1] - &cost[1] = ( k + 1 ) - 1 =
        // k。 所以 ans 正好就是满足条件 cost[i] <= t 的最大
        // i，也就是能解决的最大问题数。 注意：upper_bound 是 C++
        // 标准库算法，C++98 即支持，C++11/14/17/20 均可使用。
        int ans = std::upper_bound(cost + 1, cost + 1 + n, t) - (cost + 1);
        std::cout << ans << "\n";
    }

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年1月25日

luogu-P2440 木材加工