跳转至

进阶贪心和二分

选我

错误的贪心是按照 $a_i+b_i$ 升序排序。例如下面例子。

$a_i$ $b_i$ $a_i+b_i$ $2a_i+b_i$
$1$ $100$ $101$ $102$
$50$ $50$ $100$ $150$
$51$ $49$ $100$ $151$

如果按照 $a_i+b_i$ 从大到小排序，需要演讲 $2$ 次才能获胜。而只需要去第三个地方演讲一次即可直接获胜。

聪聪老师的目标是：让自己的总票数 大于 翁老师的总票数。

我们先设：

  • 不演讲时，聪聪老师得票为 $0$（因为支持他的人不投票），
  • 翁老师得票为：$\sum a_i$

每演讲一个片区 $i$：

  • 聪聪老师获得该片区的所有人投票，即：$a_i + b_i$

  • 翁老师失去该片区原本支持他的人，即损失：$a_i$

🎯 所以，每演讲一个片区 $i$，聪聪老师的净收益是：

\[ \Delta_i = (a_i + b_i) + a_i = 2a_i + b_i \]

解释：$a_i + b_i$：该片区的所有人都改投聪聪老师。$a_i$：这些原本是支持翁老师的票，现在转而支持聪聪老师，等于从对方阵营中抢票，实际上聪聪 多赚 了这部分票

✅ 正确贪心策略：

将每个片区按照 $\Delta_i = 2a_i + b_i$ 从大到小排序，依次选择发表演讲，直到：

\[ \text{聪聪老师的票数} > \text{翁老师的票数} \]

这就是本题最优解的核心逻辑。

[GESP202503 五级] 平均分配

✅ 正确解法思路（贪心）

  • 第一步：假设所有物品都卖给 B

    • 初始总收入为：$\text{sum} = \sum\limits_{i=1}^{2n} b_i$

  • 第二步：从中挑出 $n$ 件退还给 C（也就是卖给 C）

    • 对于每件物品，计算 如果卖给 C 而不是 B，多赚（或少亏）多少钱：$\delta_i = c_i - b_i$

  • 选择 $n$ 个最大的 $\delta_i$，也就是收益从 B 转到 C 后增益最大的 $n$ 件物品

  • 第三步：总收入为

\[ \text{ans} = \sum b_i + \sum_{\text{top n}} (c_i - b_i) \]

区间贪心模型

模型一：线段覆盖模型

题意： 给定 $n$ 个区间，最多可以选择多少个没有重叠的区间。

解题思路：

  • 按照右端点从小到大排序。
    • 贪心选择区间，每次选择右端点最小的区间，并判断是否与已选择的区间有重叠。
    • 如果有重叠，则不能选择该区间。
  • 具体来说：维护上一个选择的区间的右端点数值 endr。
    • 若当前区间 a[i].l > endr 说明没有交集。可以选择。
    • 否则无法选择。
  • 时间复杂度：$O(n\log n)$

模型二：最少点覆盖

题意： 给定 $n$ 个区间 和一条无限长的数轴。要求在数轴上选择若干个点，使得每个区间至少有一个点被选中。求最少选择几个点。

解题思路：

  • 按照区间的右端点从小到大排序。
    • 在当前区间内随便选一个点都能覆盖当前区间。
    • 为了减少后续的选择，应当把点选择到区间的右端点处，这样尽可能照顾到后面的区间。
  • 维护一个 endr，记录上一个选择的点的位置。
    • 若 a[i].l > endr 说明当前区间没有被覆盖到。
    • 更新 endr = a[i].r。同时 sum++ 相当于选择了一个点。
  • 时间复杂度：$O(n\log n)$

[ABC230D] Destroyer Takahashi

本题相当于一次性选择一个长度为 $D$ 的区间来覆盖目前这些区间，使得每个区间都被覆盖过。和模型二类似，按照右端点从小到大排序，并维护一个 endr，记录上一个选择的点位置。

注意更新 endr = a[i].r + D - 1 相当于选择的最远的点再 a[i].r + D - 1 这个位置。

其余常见模型

知乎

简单例题

一：序列

题意： 给定 $n$ 个区间，要求每个区间至少有 $c$ 个点，问你最少需要多少个点。

解题思路：

  • 按照右端点从小到大排序。
  • 使用一个 vis 数组打标记，标记已经选择的点的位置。
  • 遍历所有区间 [l, r, c]。
    • 首先统计当前区间内 vis 值为 $1$ 的个数，记为 cnt。
    • 若 cnt >= c 说明当前区间内已经有 c 个点，不需要选择。
    • 否则，选择 c - cnt 个点，并更新 vis 数组。
    • 倒序遍历当前区间，将点选择尽量靠右的位置。以使得照顾尽量靠后的位置。

二：雷达安装

针对每个岛屿可以使用勾股定理求出 $x$ 轴上最右边的雷达位置 $r$ 以及最左边的雷达位置 $l$。

  • 则在区间 $[l,r]$ 随便选择一个点都可以覆盖到当前岛屿。

那么问题就是有 $n$ 个 $[l,r]$ 区间，最少选择几个点使得每个区间都至少有一个点。

三：[CSP-S 2024] 超速检测

基本方向：按照 $a_i$ 的值分三种情况。$>0,=0,<0$。

  • $a_i=0$，速度恒定不变。因此初始速度 $v_i>V$ 则超速。
    • 是否会被摄像头拍到？
    • 等价于求解是否存在一个摄像头，其位置 $\geq d_i$。
      • 可以二分 lower_bound。
if (a[i] == 0) // 速度不变
{
    if (v[i] > V) // 初始速度必须大于限速
    {
        int l = lower_bound(p + 1, p + m + 1, d[i]) - p;
        if (l != m + 1) // 会被拍到
        {
            ans++;
        } 
    }   
}
  • $a_i>0$。
    • 若初始 $v_i>V$ 初始就超速，则等同于 $a_i=0$。
    • 若 $v_i\leq V$，则前进了一段距离 $s$ 以后才超速。求出前近距离 $s$，然后等同于求解 $d_i+s\leq L$ 是否存在一个摄像头。

根据题目给的公式 $s=\dfrac{V^2-v_i^2}{2a_i}$ ，可以得到当 $s> \dfrac{V^2-v_i^2}{a_i}$ 会超速。

由于摄像头都在整数位置，因此 $s$ 应该取 $\left\lfloor\dfrac{V^2-v_i^2}{a_i}\right\rfloor+1$。

例如：

  • $s=3.5$，下取整以后为 $3$，然后加 $1$ 得到 $4$。
  • $s=3$，下取整以后为 $3$，然后加 $1$ 仍然得到 $4$。
if (a[i] > 0)
{
    if (v[i] > V) // 超速
    {
        int j = lower_bound(p + 1, p + m + 1, d[i]) - p;
        if (j != m + 1) // 说明可以被 [j, m] 都拍一次 
        {
            ans++;
        } 
    }
    else
    {
        int s = (V * V - v[i] * v[i]) / (2 * a[i]) + 1;
        int j = lower_bound(p + 1, p + m + 1, d[i] + s) - p;
        if (j != m + 1) // 说明可以被 [j, m] 都拍一次 
        {
            ans++;
        }  
    } 
}
  • $a_i<0$：
    • 若 $v_i\leq V$，则永远不超速不必考虑。
    • 反之，超速了一段距离 $s$ 以后速度降了下来。
    • 因此需要求出前进距离 $s$，满足 $[d,d+s]$ 都是超速的。然后判断这个范围是否存在摄像头即可。

根据题目给的公式 $s=\dfrac{V^2-v_i^2}{2a_i}$ ，可以得到当 $s< \dfrac{V^2-v_i^2}{a_i}$ 会超速。

由于摄像头均在整数位置，因此 $s$ 应该取 $\lceil\dfrac{V^2-v_i^2}{a_i}-1\rceil$。

例如：

  • $s=3.5$，实际前进 $3$ 以内都是超速的，因此摄像头应该在 $[d,d+3]$ 之间。
  • $s=3$，实际前进 $2$ 以内都是超速的，因此摄像头应该在 $[d,d+2]$ 之间。

具体实现也可以：

  • 记 up = V * V - v[i] * v[i]，down = 2 * a[i]。
  • 令 s = up / down。由于结果必然非负，相当于下取整。
  • 若 up % down == 0，给 $s$ 减去 $1$ 即可。
if (a[i] < 0)
{
    if (v[i] > V) // 初始超速才有可能被抓到
    {
        int up = V * V - v[i] * v[i], down = 2 * a[i];
        int s = up / down;
        if (up % down == 0) s -= 1;
        // 验证 [d, d + s] 以内有无摄像头 
        int l = lower_bound(p + 1, p + m + 1, d[i]) - p;
        if (l != m + 1)
        {
            // 二分最后一个小于等于 d[i] + s 的摄像头编号记作 r 
            int r = upper_bound(p + 1, p + m + 1, d[i] + s) - p - 1;
            if (l <= r)
            {
                ans++;
            } 
        }
    } 
}

再来看第二问

求解最多关闭个数等于同于总数减去最少开启数量。

注意到：每辆车都对应一个摄像头区间，只要在该区间内的任意一个摄像头均可拍到该车超速。

  • 例如当 $a_i=0$ 时，第一个摄像头 $j$ 可以拍到，则 $[j,m]$ 的摄像头也都可以拍到。

问题等价于：给定若干个区间 $[l,r]$，每个区间至少有一个点（摄像头），问至少选择几个点。

显然就是最少点覆盖模型了，按照右端点从小到大排序贪心即可。

最终整体复杂度为 $O(n\log{m})$。

完整代码

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
int n, m, L, V, d[N], v[N], a[N], p[N];
struct node 
{
    int l, r;
};
bool cmp(node x, node y) 
{
    return x.r < y.r; 
}
void solve()
{
    // 枚举所有的车，检验是否超速 
    int ans = 0;
    vector<node> segs;
    for (int i = 1; i <= n; i++) 
    {
        if (a[i] == 0)
        {
            if (v[i] > V) // 超速
            {
                int j = lower_bound(p + 1, p + m + 1, d[i]) - p;
                if (j != m + 1) // 说明可以被 [j, m] 都拍一次 
                {
                    ans++;
                    segs.push_back({j, m});
                } 
            } 
        }
        if (a[i] > 0)
        {
            if (v[i] > V) // 超速
            {
                int j = lower_bound(p + 1, p + m + 1, d[i]) - p;
                if (j != m + 1) // 说明可以被 [j, m] 都拍一次 
                {
                    ans++;
                    segs.push_back({j, m});
                } 
            }
            else
            {
                int s = (V * V - v[i] * v[i]) / (2 * a[i]) + 1;
                int j = lower_bound(p + 1, p + m + 1, d[i] + s) - p;
                if (j != m + 1) // 说明可以被 [j, m] 都拍一次 
                {
                    ans++;
                    segs.push_back({j, m});
                }  
            } 
        }
        if (a[i] < 0)
        {
            if (v[i] > V)
            {
                int up = abs(V * V - v[i] * v[i]), down = abs(2 * a[i]);
                int s = up / down;
                if (up % down == 0) s -= 1;
                // 验证 [d, d + s] 以内有无摄像头 
                int l = lower_bound(p + 1, p + m + 1, d[i]) - p;
                if (l != m + 1)
                {
                    // 二分最后一个小于等于 d[i] + s 的摄像头编号记作 r 
                    int r = upper_bound(p + 1, p + m + 1, d[i] + s) - p - 1;
                    if (l <= r)
                    {
                        ans++;
                        segs.push_back({l, r});
                    } 
                }
            } 
        }
    }
    cout << ans << " ";
    int endr = -1, sum = 0;
    sort(segs.begin(), segs.end(), cmp);
    for (auto it : segs)
    {
        if (it.l > endr)
        {
            endr = it.r;
            sum++;
        }
    }
    cout << m - sum << "\n"; 
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) 
    {
        cin >> n >> m >> L >> V;
        for (int i = 1; i <= n; i++) cin >> d[i] >> v[i] >> a[i];
        for (int i = 1; i <= m; i++) cin >> p[i];
        solve(); 
    }
    return 0;
}

邻项交换法

它是一种常见的交换论证技巧，本质是：

  • 通过交换两个局部选择的顺序，来证明某种贪心策略是最优的。

举个例子： 有 $n$ 个任务，第 $i$ 个任务加工时间是 $t_i$。你要安排这些任务顺序，使得 所有任务的总等待时间之和最小。

贪心策略： 按照加工时间 $t_i$ 从小到大的顺序安排任务。

证明：

假设当前排了某两个任务 $i,j$，其中 $t_i>t_j$。

若 $i$ 在 $j$ 前面。此时等待时间为：

  • $i$ 等待 $W$。$j$ 等待 $W+t_i$。
    • 其中 $W$ 指 $i$ 之前任务的等待总时间。
  • 合计等待时间为 $2W+t_i$。

若 $j$ 在 $i$ 前面。此时等待时间为：

  • $j$ 等待 $W$。$i$ 等待 $W+t_j$。

  • 合计等待时间为 $2W+t_j$。

显然，$2W+t_i>2W+t_j$。

所以最优策略是：把处理时间短的任务排在前面。

例题一：[USACO05NOV] 奶牛玩杂技

设当前前 $i-1$ 头牛的重量和为 $sum$。

若 $i$ 在 $j$ 之前：

  • 对于 $j$ 的压扁程度为：$sum + w_i - s_j$
  • 对于 $i$ 的压扁程度为：$sum - s_i$
  • 最大压扁程度为：$\max(sum - s_i, sum + w_i - s_j)$

若 $j$ 在 $i$ 之前：

  • 对于 $i$ 的压扁程度为：$sum + w_j - s_i$
  • 对于 $j$ 的压扁程度为：$sum - s_j$
  • 最大压扁程度为：$\max(sum - s_j, sum + w_j - s_i)$

推导比较

为了使总压扁程度更小，希望满足：

\[ \max(sum - s_i, sum + w_i - s_j) < \max(sum - s_j, sum + w_j - s_i) \]

记：

  • $1 = sum - s_i$
  • $2 = sum + w_i - s_j$
  • $3 = sum - s_j$
  • $4 = sum + w_j - s_i$

接下来分类讨论左右两边 $\max$ 取到的项。

  • 若左边取 $1$，右边取 $3$：

$1 < 3 \quad \Rightarrow \quad sum - s_i < sum - s_j$

显然恒成立，因为 $s_i > s_j$ 导致 $sum - s_i < sum - s_j$。

  • 若左边取 $1$，右边取 $4$：

$1 < 4 \quad \Rightarrow \quad sum - s_i < sum + w_j - s_i$ 恒成立，因为 $w_j > 0$。

  • 若左边取 $2$，右边取 $3$：

$2 < 3 \quad \Rightarrow \quad sum + w_i - s_j < sum - s_j$ 这不可能成立，因为 $w_i > 0$。

  • 若左边取 $2$，右边取 $4$：

$2 < 4 \quad \Rightarrow \quad sum + w_i - s_j < sum + w_j - s_i$ 化简得： $w_i + s_i < w_j + s_j$

因此，应按照 $w + s$ 从小到大排序。

例题二：[ABC268F] Best Concatenation

题意概述

有 $n$ 个字符串 $s_1,s_2,\ldots,s_n$。找到最优顺序将 $n$ 个字符串拼起来并使得总得分最大。

得分规则：

  • 遍历最终的字符串 $S$，若 $S[i]$ 为数字字符，开始计算得分。
  • 该得分为：$S[i]$ 对应的数字 乘以 从头开始到当前位置字符 X 的个数。
  • 累加所有得分即为总得分。

数据范围：$n \le 2 \times 10^5$

解题思路（一）：邻项交换法介绍

使用贪心 + 邻项交换法：我们要决定两个字符串 $s_i$ 和 $s_j$ 的先后顺序是否影响最终得分。

定义每个字符串 $s_i$ 的三个关键量：

  • $x_i$：字符串中字符 X 的数量
  • $d_i$：数字字符的总和（贡献因子）
  • $\text{score}_i$：$s_i$ 内部自带的得分（数字字符和 乘以 当前已有的 X 数）

假设当前已有 $sum_x$ 个 X，若拼接顺序为 $s_i$ 在前、$s_j$ 在后，计算其额外贡献。

解题思路（二）：排序不等式推导

  • $s_i$ 在 $s_j$ 之前的额外贡献为： $d_i \cdot sum_x + d_j \cdot (sum_x + x_i)$

  • $s_j$ 在 $s_i$ 之前的额外贡献为： $d_j \cdot sum_x + d_i \cdot (sum_x + x_j)$

  • 两者差值为： $d_j \cdot x_i - d_i \cdot x_j$

若希望 $s_i$ 在 $s_j$ 前更优，应满足： $x_i \cdot d_j > x_j \cdot d_i$

排序策略：按照 $(x_i, d_i)$ 对，每对字符串比较时应用上述交叉乘排序规则。

具体实现步骤

  • 遍历每个字符串，预处理出：

    • 内部得分 $\text{score}_i$
    • $x_i$（字符 X 数量）
    • $d_i$（数字字符和）

  • 将字符串封装为结构体，按照 $x_i \cdot d_j > x_j \cdot d_i$ 的顺序排序。

  • 排序后拼接字符串，逐字符扫描，计算最终得分。

时间复杂度： $O(n \log n + \text{总字符数})$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 2e5 + 5;
int n;
struct node
{
    ll x, d, score;
} a[N];
bool cmp(node a, node b)
{
    return a.x * b.d > a.d * b.x;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        ll x = 0, d = 0, score = 0;
        for (char c : s)
        {
            if (c == 'X')
                x++;
            else if (isdigit(c))
            {
                d += c - '0';
                score += (c - '0') * x;
            }
        }
        a[i] = {x, d, score};
    }
    sort(a + 1, a + n + 1, cmp);
    ll sumx = 0, ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += a[i].d * sumx + a[i].score;
        sumx += a[i].x;
    }   
    cout << ans;
    return 0;
}

重要二分函数

lower_bound和upper_bound。

  • lower_bound 返回数组中第一个 $\ge x$ 的元素的位置
  • upper_bound 返回数组中第一个 $\gt x$ 的元素位置

用法：

int pos = lower_bound(a, a + n, x) - a; // 减去数组名才能得到下标
if (pos == n) 
    cout << "-1"; // 说明不存在大于或等于 x 的元素
else 
    cout << a[pos];

pos = lower_bound(a + 1, a + n + 1, x) - a; // upper_bound
if (pos == n + 1) 
    cout << "-1"; // 说明不存在大于或等于 x 的元素
else 
    cout << a[pos];

实数二分

实数二分常用于求解数值问题，例如求一个数的平方根、立方根，或在实数范围内进行“二分答案”的问题。

与整数二分相比，实数二分的区别仅在于使用 double 类型，并使用精度控制结束条件。

问题： 由于浮点数在计算机中采用二进制近似存储，很多实数无法被精确表示，因此直接使用== 判断两个浮点数是否相等可能出现误差。

因此，在实数二分中，我们通常使用精度控制结束条件，即判断两个实数之间的距离是否小于某个阈值。

写法

通常设定一个很小的正数 $\varepsilon$，当左右边界相差小于 $\varepsilon$ 时，就认为已经“足够精确”。

例如：while (l + eps < r)。设置 constexpr double eps = 1e-6 这样的小数字。

例题一：数的三次方根

本题要求求出一个实数 $x$，使得 $x^3 = n$。

首先要确认能否使用二分。由于立方函数 $f(x) = x^3$ 是严格单调递增的（即 $x$ 增大时 $x^3$ 也一定增大），满足单调性条件，因此可以使用二分法来求解。

  • 设定一个足够大的查找区间，例如 $l = -100$, $r = 100$。
  • 每次取中点：$mid = \frac{l + r}{2}$，然后比较 $mid^3$ 和 $n$ 的大小关系：
    • 如果 $mid^3 \geq n$，说明答案可能在左边，设 $r = mid$
    • 如果 $mid^3 < n$，说明答案在右边，设 $l = mid$

注意：由于是实数二分，不要再使用 +1 或 -1 来收缩边界，而是使用一个 $\varepsilon$ 控制精度，如 $1e-8$。

double l = -100, r = 100;
while (l + eps < r)
{
    double mid = (l + r) / 2;
    if (mid * mid * mid > n) 
        ans = mid, r = mid;
    else 
        l = mid;
}
printf("%.6lf", ans);

例题二：包裹快递

题意： 小 K 需依次送 $n$ 个包裹，每个地点有一个可签收时间段 $[x_i, y_i]$。

每两个地点之间有距离 $s_i$，车速为 $v$，K 可以提前到达并等待，但不能迟到。

目标：求满足送达所有包裹的前提下，车的最小最大速度 $v$

观察： 速度越快越容易满足送达条件，具备单调性 考虑二分速度 $v$。

边界设置：

  • $l = \varepsilon$，如 $1e^{-6}$（避免除以 0）
  • $r = 1e7$（足够大的速度）

Check 函数设计

bool check(double v)：判断当前速度 $v$ 是否能在所有地点按时送达。

设当前时间为 $now$，初始为 $0$，依次遍历每个包裹：

  • 计算到达时间：$now + \frac{s_i}{v}$
  • 若超出 $[x_i, y_i]$ 范围（即超过 $y_i$） → 不合法
  • 若早于 $x_i$，需等待：$now = x_i$
  • 否则：正常送达，更新 $now = now + \frac{s_i}{v}$

注意： 本题卡精度，需要使用 long double 类型。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
const double eps = 1e-6;
int n;
long double x[N], y[N], s[N];
bool check(long double v)
{
    long double now = 0; // 当前时间初始为 0
    for (int i = 1; i <= n; i++)
    {
        double t = s[i] / v; // 计算走过去的时间
        if (now + t > y[i]) return false;
        else if (now + t < x[i])
        {
            now = x[i]; // 当前到达时间是 x[i]
        }
        else
        {
            now = now + t;
        }
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> s[i];
    long double l = 0, r = 1e7, ans;
    while (l + eps < r)
    {
        long double mid = (l + r) / 2;
        if (check(mid)) ans = mid, r = mid;
        else l = mid;
    }
    cout << fixed << setprecision(2) << ans;
    return 0;
}

机器人的情感

本题属于中位数常见的二分套路。二分中位数 $x$。

对于整个序列，将大于等于 $x$ 看作是 $1$，小于 $x$ 看作是 $-1$。

若可以找到一个区间，且区间和为 $0$，说明该区间中位数大于等于 $x$。

区间和可以用前缀和高效处理，但枚举区间显然会 TLE。让我们这样审视以下问题：

当二分中位数 $x$ 以后，即找到一个区间 $[i,j]$ 使得：

\[\begin{cases} j-i+1\geq L\\ sum_j-sum_{i-1}\geq 0 \end{cases}\]

枚举 $j$，维护前缀最小值 $sum_{i-1}$ 记作 $mn$。若 $sum_j-mn\geq 0$，则存在一个区间。为了保证区间长度。 $j$ 必须从 $L$ 开始枚举。

bool check(int x)
{
    vector<int> sum(n + 1);
    for (int i = 1; i <= n; i++)
        if (a[i] >= x)
            sum[i] = sum[i - 1] + 1;
        else 
            sum[i] = sum[i - 1] - 1;
    int mn = 1e9;
    for (int j = L; j <= n; j++)
    {
        mn = min(mn, sum[j - L]);
        if (sum[j] - mn >= 0) return true;
    }
}

例题四：[NOIP2011 提高组]聪明的质监员

对于一个区间 $[l_i,r_i]$ 来说，检验值 $y_i$

\[ y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j \]

此式子概括来说就是：区间内大于等于 $W$ 的个数乘以大于等于 $W$ 的 $w$ 之和。

随着 $W$ 的增大，$y_i$ 必然减小。那么 $\sum y_i$ 也在减小。因此 $W$ 具备单调性存在一个临界值使得其和 $|s-\sum y_i|$ 最小。

因此二分 $W$ 尝试找到最接近 $s$ 的 $\sum {y_i}$。

🛠️ 二分解法整体流程

1. 二分查找：

我们设定搜索范围：

  • $W \in [1, 10^6]$，因为矿石重量最大是 $10^6$

每次二分一个中值 $W_{\text{mid}}$，然后：

  • 预处理满足 $w_i \ge W_{\text{mid}}$ 的个数以及前缀和。
    • 通过前缀和 $O(1)$ 的时间求出 $y_i$。
  • 对每个区间，计算 count 和 sum
  • 得到当前 $y(W_{\text{mid}})$，和 $s$ 比较大小，更新最小 $|y - s|$
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
ll s;
vector<int> w, v;
vector<pair<int, int>> ranges;

ll calc_y(int W) 
{
    vector<int> cnt(n + 1, 0);
    vector<ll> sum(n + 1, 0);

    for (int i = 1; i <= n; ++i) 
    {
        cnt[i] = cnt[i - 1] + (w[i] >= W ? 1 : 0);
        sum[i] = sum[i - 1] + (w[i] >= W ? v[i] : 0);
    }

    ll y = 0;
    for (auto [l, r] : ranges) 
    {
        int c = cnt[r] - cnt[l - 1];
        ll s = sum[r] - sum[l - 1];
        y += c * s;
    }
    return y;
}

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

    cin >> n >> m >> s;
    w.assign(n + 1, 0);
    v.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i) 
    {
        cin >> w[i] >> v[i];
    }
    ranges.assign(m, {});
    for (int i = 0; i < m; ++i) 
    {
        cin >> ranges[i].first >> ranges[i].second;
    }

    int L = 1, R = 1e6;
    ll ans = LLONG_MAX;

    while (L <= R) 
    {
        int mid = (L + R) / 2;
        ll y = calc_y(mid);
        ans = min(ans, abs(y - s));

        if (y > s) 
        {
            L = mid + 1;
        } 
        else 
        {
            R = mid - 1;
        }
    }

    cout << ans << '\n';
}