这道题最关键的转变是：

不要正着决定“今天让谁逃离”，而要倒着计算“让 $k$ 个孩子全部逃离，还缺多少奖牌”。

下面先建立一个共用的状态，再分别讲两种维护方法：

• 解法一：倒序贪心＋小根堆，$O(N\log N)$。
• 解法二：凸 DP＋双端队列，$O(N)$。

第二种做法会把两个操作合并起来，避免实现比较繁琐的折线求交。

一、共同的建模

1. 只考虑最终会逃离的孩子

可以只给最终会逃离的孩子分配奖牌，其他孩子第一天就不管了。帮助一个最终不能逃离的孩子，没有必要。官方题解也使用了这一化简。(AtCoder)

由于每天会收回所有奖牌并重新分配，我们只需要知道：

还有多少个孩子，以及他们一共有多少奖牌。

不需要知道每个人分别拿着多少奖牌。多出来的奖牌可以交给尚未逃离的孩子保管；即使达到 $C_i$，也可以选择不逃离。

2. 倒序定义状态

设

$$f_i(k)= \text{第 }i\text{ 天开始时有 }k\text{ 个孩子，要求他们最终全部逃离，}$$ $$\text{在领取 }A_i\text{ 之前，最少需要已有多少奖牌。}$$

最后一天之后，不能再让任何孩子逃离，所以

$$f_{N+1}(0)=0,\qquad f_{N+1}(k)=+\infty\quad(k>0).$$

考虑第 $i$ 天，假设这 $k$ 个孩子中，有 $j$ 个留到以后逃离，另外 $k-j$ 个今天逃离。

那么需要：

• 给所有人支付今天的费用：$kB_i$；
• 让今天逃离的人带走奖牌：$(k-j)C_i$；
• 给以后逃离的人留下至少 $f_{i+1}(j)$ 枚奖牌。

当天还能得到 $A_i$ 枚奖牌，因此

$$\boxed{ f_i(k)= \max\left( 0,\; kB_i-A_i+ \min_{0\le j\le k} \bigl(f_{i+1}(j)+(k-j)C_i\bigr) \right). }$$

答案就是满足 $f_1(k)=0$ 的最大 $k$。

这个转移本身很慢，但接下来会发现：不必逐个保存 $f_i(k)$。

3. 人数只需要考虑到 $10^6+1$

所有最终逃离的孩子，第一天都必须支付 $B_1$，所以

$$\text{答案}\le \left\lfloor\frac{A_1}{B_1}\right\rfloor\le 10^6.$$

两份代码都取

cpp
const long long LIMIT = 1000001;

只需要保证前 LIMIT 个人对应的状态正确即可。这里不会真的开出这么多状态，而是把相同的值压缩成一段。

---

二、解法一：倒序贪心＋小根堆

第一种做法的核心是：将代价相同的若干项打包放进小根堆，每次优先处理最小代价，并允许最后一项只支付一部分。(Luogu)

不过，首先必须讲清楚：这里的“代价”到底是什么。

1. 不保存总费用，保存“多逃离一个人”的增量

固定一天，把相邻状态之差记作

$$d_k=f(k)-f(k-1).$$

于是

$$f(k)=d_1+d_2+\cdots+d_k.$$

我们维护的是一个非降序列：

$$d_1\le d_2\le d_3\le\cdots.$$

它的含义是：

从“最优地让 $k-1$ 个人逃离”，变成“最优地让 $k$ 个人逃离”，需要额外准备多少奖牌。

这不是某个指定孩子的固定花费。 当目标人数改变时，最优的逃离安排也可以改变。

下面的转移既能维护这些增量，也会保持它们非降，因此不需要提前假定这一性质成立。

2. 倒着加入第 $i$ 天，需要做三件事

第一件：原来的所有增量加上 $B_i$

原来的方案让孩子在第 $i+1$ 天及以后逃离。

现在多考虑了第 $i$ 天，每个孩子必须先支付今天的 $B_i$，所以每增加一个孩子，就额外多付 $B_i$。

因此，原来的每项增量都加上 $B_i$。

第二件：加入“今天逃离”的选项

一个孩子今天逃离，需要支付

$$B_i+C_i.$$

这样的选项可以选任意多次。

所以，将原来的增量全部加上 $B_i$ 后，再加入足够多个值为 $B_i+C_i$ 的新选项，取其中最小的 $k$ 项，就得到暂时不考虑 $A_i$ 时，让 $k$ 个人逃离的最小代价。

为什么可以直接合并？

假设选了 $j$ 项旧选项，那么由于旧增量非降，一定可以选旧序列的前 $j$ 项；剩下 $k-j$ 项选今天逃离。这恰好对应 DP 中枚举 $j$ 的转移。

等价地，从差分角度看，就是先把旧差分中大于 $C_i$ 的部分压到 $C_i$，再统一加上 $B_i$。AtCoder 上另一份题解也给出了这一差分转移。(AtCoder)

堆的实现不必真的“压低所有较大值”，直接加入 LIMIT 个新选项就足够了。

第三件：用 $A_i$ 从最小增量开始抵扣

设前两步处理后的增量是

$$d_1\le d_2\le \cdots.$$

得到 $A_i$ 枚奖牌后，新的总费用应当是

$$\max(0,d_1+\cdots+d_k-A_i).$$

它对应的增量变化非常简单：

从左到右抵扣，前面若干项变成 $0$，至多一项被部分抵扣，其余项不变。 这也是上述差分题解对 $A_i$ 的处理方式。(AtCoder)

例如：

$$(3,5,8,\ldots),\qquad A_i=6$$

会变成

$$(0,2,8,\ldots).$$

因为第一项用掉 $3$ 枚奖牌，剩下 $3$ 枚继续抵扣第二项。

这也说明了为什么不能随意把剩余奖牌摊到很多项上：我们要维护的是每一个前缀的最优总费用。

3. 一个特别容易错的地方

变成 $0$ 的项不能删除，必须放回堆。

它表示：

从第 $i$ 天开始，让这些孩子逃离已经不需要额外带入奖牌。

它不表示这些孩子在更早的日子里不需要花钱。

继续倒推到第 $i-1$ 天时，这些项仍然要加上 $B_{i-1}$。

4. 用“相同代价的段”压缩

堆中一个元素保存：

cpp
{value, count}

表示有 count 项增量相同。

另外用 shift 维护所有项统一加上的值：

cpp
真实增量 = value + shift

于是：

• 全体加 $B_i$：只需要 shift += b[i]；
• 加入真实代价为 $B_i+C_i$ 的新选项：存入 b[i] + c[i] - shift；
• 抵扣 $A_i$：不断取出堆顶，整段抵扣；最后一段至多拆出一个被部分抵扣的项。

每一天处理 $A_i$ 之前，每项真实增量至少为 $B_i\ge1$，因此代码中的除法不会遇到零。

5. 样例中的增量变化

第一组样例，倒序处理后的前几项增量如下。注意，这不是孩子手中的奖牌分布，而是 $f_i$ 的差分。

处理完哪一天	前几项增量
第 $4$ 天	$0,0,10,10,\ldots$
第 $3$ 天	$2,3,8,8,\ldots$
第 $2$ 天	$0,0,0,6,6,\ldots$
第 $1$ 天	$0,0,0,0,0,5,\ldots$

最终前 $5$ 项都是零，所以答案为 $5$。

6. 正确性与复杂度

每一轮的“整体加 $B_i$、加入今天逃离的选项、抵扣 $A_i$”都恰好实现了 DP 转移，因此最终维护的就是 $f_1$ 的增量。

增量非负，所以前面连续零增量的数量，就是最大的满足 $f_1(k)=0$ 的 $k$。

每轮只会新建常数个段；整段弹出的段会消失，至多最后一段需要拆开。因此总堆操作次数为 $O(N)$。

时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。

7. C++17 代码

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

using ll = long long;

struct Block {
    ll value, count;

    // priority_queue 默认大根堆，这里反过来比较。
    bool operator<(const Block& other) const {
        return value > other.value;
    }
};

ll solve() {
    int n;
    cin >> n;

    vector<ll> a(n + 1), b(n + 1), c(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }

    const ll LIMIT = 1000001;

    priority_queue<Block> heap;

    // 堆中 value + shift 才是真实增量。
    ll shift = 0;

    for (int i = n; i >= 1; --i) {
        // 以后逃离的孩子，也要支付今天的 B。
        shift += b[i];

        // 新增“今天逃离”的选项。
        heap.push({b[i] + c[i] - shift, LIMIT});

        ll money = a[i];
        ll zeroCount = 0;

        while (money > 0) {
            Block cur = heap.top();
            heap.pop();

            ll unit = cur.value + shift;

            if (unit * cur.count <= money) {
                // 这一整段都能被抵扣到 0。
                money -= unit * cur.count;
                zeroCount += cur.count;
            } else {
                // 先抵扣若干完整项。
                ll paid = money / unit;
                ll rest = money % unit;

                zeroCount += paid;
                cur.count -= paid;

                // 剩余奖牌至多部分抵扣一项。
                if (rest > 0) {
                    heap.push({cur.value - rest, 1});
                    --cur.count;
                }

                if (cur.count > 0) {
                    heap.push(cur);
                }

                money = 0;
            }
        }

        // 零增量也必须保留，前面的日子还要继续收费。
        if (zeroCount > 0) {
            heap.push({-shift, zeroCount});
        }
    }

    if (heap.top().value + shift == 0) {
        return heap.top().count;
    }
    return 0;
}

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

    int T;
    cin >> T;

    while (T--) {
        cout << solve() << '\n';
    }

    return 0;
}

---

三、解法二：凸 DP＋双端队列

第二种路线是维护最优代价函数的单调斜率，把相同斜率压成一段，并用双端队列维护。你给出的第二份题解采用的正是这个方向。(Luogu)

这里换一种记账方式，让“统一增加 $B_i$”消失。

1. 把以前每天的固定费用加进函数

设

$$S_i=B_1+B_2+\cdots+B_i,\qquad S_0=0.$$

定义

$$g_i(k)=f_i(k)+kS_{i-1}.$$

也就是说，除了原本需要带入的奖牌，还把这 $k$ 个孩子在前 $i-1$ 天必须支付的固定费用记到账上。

这只是给 $f_i$ 加上一条已知直线。最后 $S_0=0$，所以

$$g_1(k)=f_1(k),$$

答案没有改变。

将

$$f_{i+1}(j)=g_{i+1}(j)-jS_i$$

代入共用的 DP 转移，可以得到

$$\boxed{ g_i(k)= \max\left( kS_{i-1},\; \min_{0\le j\le k} \left[g_{i+1}(j)+(k-j)(S_i+C_i)\right]-A_i \right). }$$

这个式子可以分成两步处理。

其中的下界是 $kS_{i-1}$，不是 $0$。

因为我们额外加进了以前的固定费用，领取今天的 $A_i$ 时，不能把这些费用也抵扣掉。未来得到的奖牌，不能反过来支付以前每天的 $B$。

2. 用双端队列保存斜率

对于整数函数，相邻状态之差就是这里所说的“斜率”。

我们维护的斜率具有两个性质：

斜率非降；处理完第 $i$ 天后，每条斜率至少为 $S_{i-1}$。

相同斜率保存成一个段：

cpp
{value, count}

这里 value 就是实际斜率，不需要整体加法标记。

下面的两步会保持这些性质。

3. 第一步：从队尾把较大的斜率压下来

先看转移中的

$$\min_{0\le j\le k} \left[g_{i+1}(j)+(k-j)(S_i+C_i)\right].$$

每多选一个“今天逃离”的孩子，费用都是 $S_i+C_i$。

因此，原来某项斜率超过 $S_i+C_i$ 时，不如改用今天逃离的选项。

所以这一部分的作用就是：

$$\boxed{\text{把所有大于 }S_i+C_i\text{ 的斜率改成 }S_i+C_i.}$$

由于斜率非降，需要修改的部分一定是一个后缀。

于是从队尾不断弹出斜率不小于 $S_i+C_i$ 的段，将长度相加，再放回一个斜率为 $S_i+C_i$ 的段即可。把等于的段一起弹出，只是为了合并相同斜率。

这里始终只维护前 LIMIT 项。处理最后一天时，直接将它们全部初始化为 $S_N+C_N$。

4. 第二步：抵扣 $A_i$，但不能低于直线 $kS_{i-1}$

现在需要执行：

将函数整体减去 $A_i$，再与直线 $kS_{i-1}$ 取最大值。

直接求两条折线的交点会比较麻烦，但可以换一个顺序理解：

先从函数中减去直线 $kS_{i-1}$，抵扣 $A_i$ 并与零取最大值，最后再把这条直线加回来。

从斜率上看，减去这条直线，就是从每条斜率中减去 $S_{i-1}$。

因此，一项斜率为 value 时，它真正需要被抵扣的部分是

$$\boxed{\text{unit}=\text{value}-S_{i-1}.}$$

不是整个 value。

于是仍然可以从队首开始处理：

• 一项被完全抵扣后，斜率变成 $S_{i-1}$；
• 一项被部分抵扣后，斜率减去用在它上面的奖牌数；
• 后面的项不变。

例如，当前下界斜率为 $4$，原来的斜率为

$$(7,9,12,\ldots),$$

真正要抵扣的部分就是

$$(3,5,8,\ldots).$$

若 $A_i=6$，抵扣后变成

$$(0,2,8,\ldots),$$

再加回下界斜率 $4$，得到

$$(4,6,12,\ldots).$$

这就将“整体减去 $A_i$”和“与下界直线取最大值”合并成了一次队首处理。

5. 为什么这样操作始终合法？

处理第 $i$ 天之前，维护的是 $g_{i+1}$，其斜率至少为 $S_i$。

第一步用来压低斜率的上限是 $S_i+C_i$，它也不小于 $S_i$。所以第一步之后，每条斜率仍至少为 $S_i$。

于是第二步中的

$$\text{unit} =\text{value}-S_{i-1} \ge S_i-S_{i-1} =B_i >0.$$

抵扣之后，斜率序列的形态是：

若干项 $S_{i-1}$，至多一项被部分抵扣的斜率，剩余不变的斜率。

它仍然非降，而且每项都至少为 $S_{i-1}$。

所以这两个性质可以一直保持，双端队列的两端操作也始终正确。

6. 答案与复杂度

到第 $1$ 天时，下界斜率是 $S_0=0$，并且 $g_1=f_1$。

因此，队首零斜率段的长度就是答案；如果队首斜率不是零，答案就是零。

每轮在队首、队尾只会新建常数个段。被整段弹出的段不再存在，部分处理只会发生在当前操作的最后一段，所以总操作次数为 $O(N)$。

时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。

7. C++17 代码

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

using ll = long long;

struct Block {
    ll value, count;
};

ll solve() {
    int n;
    cin >> n;

    vector<ll> a(n + 1), b(n + 1), c(n + 1);
    vector<ll> sum(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i] >> c[i];
        sum[i] = sum[i - 1] + b[i];
    }

    const ll LIMIT = 1000001;
    deque<Block> q;

    for (int i = n; i >= 1; --i) {
        // 第一步：将较大的斜率压到 S[i] + C[i]。
        ll cap = sum[i] + c[i];

        // 最后一天没有旧状态，直接初始化 LIMIT 项。
        ll count = (i == n ? LIMIT : 0);

        while (!q.empty() && q.back().value >= cap) {
            count += q.back().count;
            q.pop_back();
        }

        if (count > 0) {
            q.push_back({cap, count});
        }

        // 第二步：抵扣 A[i]，斜率不能低于 S[i - 1]。
        ll base = sum[i - 1];
        ll money = a[i];
        ll flatCount = 0;

        while (money > 0) {
            Block cur = q.front();
            q.pop_front();

            // 只抵扣高于下界的这一部分。
            ll unit = cur.value - base;

            if (unit * cur.count <= money) {
                // 这一整段都能降到 base。
                money -= unit * cur.count;
                flatCount += cur.count;
            } else {
                ll paid = money / unit;
                ll rest = money % unit;

                flatCount += paid;
                cur.count -= paid;

                // 至多有一项被部分抵扣。
                if (rest > 0) {
                    --cur.count;
                }

                // 先放回较大的，再放回较小的。
                if (cur.count > 0) {
                    q.push_front(cur);
                }
                if (rest > 0) {
                    q.push_front({cur.value - rest, 1});
                }

                money = 0;
            }
        }

        if (flatCount > 0) {
            q.push_front({base, flatCount});
        }
    }

    if (q.front().value == 0) {
        return q.front().count;
    }
    return 0;
}

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

    int T;
    cin >> T;

    while (T--) {
        cout << solve() << '\n';
    }

    return 0;
}

四、两种解法的区别

	小根堆做法	双端队列做法
维护什么	$f_i$ 的增量	$g_i=f_i+kS_{i-1}$ 的斜率
如何加入今天逃离的选项	向堆中加入一批新代价	从队尾压低较大斜率
如何处理 $A_i$	将最小增量依次抵扣到 $0$	将最小斜率依次抵扣到 $S_{i-1}$
时间复杂度	$O(N\log N)$	$O(N)$

两种方法背后的关键是一致的：维护“增加一个逃离人数的最优增量”，而不是为某个具体孩子安排一条固定路线。

两份 C++17 程序均已通过样例、5,000 组与朴素 DP 的随机对拍，以及最大 $N$、最大 $T$ 的边界测试。