题目链接: 核心考点: [[二分]]

E. Adjusting Drones

时间限制：每测试点2秒
内存限制：每测试点256 MB

问题描述

PIXL - This Time
⠀
您正在管理一个由 $n$ 架无人机组成的机队，每架无人机有一个能量等级 $a_1,\ldots,a_n$。您还得到一个正整数 $k$，表示允许共享相同能量等级的最大无人机数量。

为了防止过载，无人机会自动执行能量平衡操作，过程如下：当存在一个能量等级出现次数严格大于 $k$ 次时，它们执行以下步骤：

1. 首先，每架无人机 $i$，如果其能量 $a_i$ 在之前出现过（即存在 $j<i$ 满足 $a_j=a_i$），则被标记；
2. 然后，对于每个被标记的无人机，其能量增加 $1$ 单位；
3. 最后，移除所有标记。

当没有任何能量等级出现次数超过 $k$ 次时，过程停止。确定将执行多少次能量平衡操作。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \leq t \leq 10^4$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $n$, $k$ ($1 \leq k \leq n \leq 2 \cdot 10^5$) — 无人机的数量和允许共享相同能量等级的最大无人机数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2n$) — 无人机的初始能量等级。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行包含一个整数：执行的能量平衡操作次数。

样例输入

5
6 3
1 1 1 1 1 1
5 1
1 3 2 1 4
6 2
1 1 1 2 3 3
4 1
8 8 8 8
2 2
1 2

样例输出

3
4
4
3
0

样例说明

在第一个测试用例中，无人机的能量等级演变如下：

• 开始时，$[1,1,1,1,1,1]$；
• 经过 $1$ 次操作后，$[1,2,2,2,2,2]$；
• 经过 $2$ 次操作后，$[1,2,3,3,3,3]$；
• 经过 $3$ 次操作后，$[1,2,3,4,4,4]$。

经过 $3$ 次操作后，每个能量等级最多出现 $3$ 次，因此过程停止。

在第二个测试用例中，能量等级变化如下：$[1,3,2,1,4] \rightarrow [1,3,2,2,4] \rightarrow [1,3,2,3,4] \rightarrow [1,3,2,4,4] \rightarrow [1,3,2,4,5]$。过程在 $4$ 次操作后停止。

赛时错误代码

// Problem: CF 2157 E
// Contest: Codeforces - Codeforces Round 1066 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2157/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    vector<int> cnt(n*3+2,0);
    for(int i=0;i<n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    int ans=0,pos;
    for(int i=1;i<=n*3;i++){
        if(cnt[i]>k){
            ans++;
            cnt[i+1]+=cnt[i]-1;
            cnt[i]=1;
        }
    }
    printf("%d\n",ans);
}


int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

💡 核心直觉 (一句话总结)

<% tp.file.cursor(2) %>

🚫 我的误区 (Fail Log)

• 思路错误: 我错误想法就是直接模拟所有的数字，跟题目解释一样，如果当前多了，那我就直接当前留一个，然后将多余的给到下一个，一直给到不能给，看操作了多少次
• 我现在暂时不清楚是不是因为看错题目的原因，我感觉我没错啊
• 实现错误:
• 数据范围:

✅ 正解思路

🧠 举一反三 (Pattern)

• 下次看到 "..." -> 想到 ...

---

💻 代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;

bool check0(vector<int>& a){
    vector<int> cnt(n*4+3,0);
    for(int i=0;i<n;i++) cnt[a[i]]++;
    for(int i=0;i<cnt.size();i++){
        if(cnt[i]>k) return false;
    }
    return true;
}

bool check(int x,vector<int>& a){
    vector<int> cnt(n*8+3,0);
    for(int i=0;i<n;i++) cnt[a[i]]++;

    vector<int> s;
    for(int i=n*4;i;i--){
        if(cnt[i]==0) s.push_back(i);
        while(cnt[i]>1&&s.size()&&s.back()<=i+x){
            cnt[i]--;
            cnt[s.back()]++;
            s.pop_back();
        }
        if(cnt[i]>1){
            cnt[i+x]+=cnt[i]-1;
            cnt[i]=1;
        }
    }
    for(int i=0;i<cnt.size();i++){
        if(cnt[i]>k) return false;
    }
    return true;
}

void solve(){

    cin>>n>>k;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    //sort(a.begin(),a.end());

    if(check0(a)){
        printf("0\n");
        return ;
    }

    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid,a)) r=mid;
        else l=mid+1;
    }

    printf("%lld\n",l);
    return ;
}


signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
````



# CF题解思路
- 元素的顺序并不重要。
- 使用 $k = 1$ 解决问题。
- 如果 $k = 1$ ，则从右到左对元素进行迭代并找到它们的最终值。
- 找出每个元素随时间变化的值。你能在固定次数 $m$ 的运算后计算出某个元素的值吗？
- 对答案进行二分搜索。
- 元素的顺序并不重要。让我们按升序对元素进行排序。此外，我们可以自由选择平局打破规则（即，哪些元素增加了 $1$ ）。-假设当所有元素都不同（即 $k = 1$ ）时，进程停止。让我们找到该点的配置 $b_1, b_2, \ldots, b_n$ 。

- 如果某些元素相等，则**最右边的**不增加。-从右到左，如果初始值为 $a_i$ ，则 $b_i$ 是 $b$ 中尚未出现的最小的 $x \geq a_i$ 。

+如果我们在一段时间内查看单个元素，它的值为 $a_i, a_i + 1, \ldots, b_i, b_i, \ldots, b_i$ 。
![[Pasted image 20251124124521.png]]


- 一个元素的最大出现次数在一次操作后不会增加（如果值 $x$ 出现 $\leq k$ 次，

它产生 $x+1$ 的 $\leq k-1$ 个副本，并且最多存在 $x+1$ 的另一个副本）. 

- 所以我们可以二分搜索答案。使用前面描述的过程，我们可以在 $O(n)$ 中的 $m$ 移动后检索配置。复杂性： $O(n \log n)$ 时间（也存在“神奇的” $O(n)$ 解决方案！


# CF 题解代码
```cpp
#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (auto &x : v) cin >> x;

    auto check_zero = [&]() {
        vector<int> freq(2 * n + 1, 0);
        for (auto x : v) ++freq[x];
        for (auto x : freq)
            if (x > k) return false;
        return true;
    };

    if (check_zero()) {
        cout << 0 << endl;
        return;
    }

    auto run = [&](int num_iter) {
        vector<int> freq(4 * n, 0);
        vector<int> zeros;
        zeros.reserve(4 * n);
        for (auto x : v) ++freq[x];
        for (int i = 4 * n; i--;) {
            if (freq[i] == 0) zeros.push_back(i);
            while (freq[i] > 1 && zeros.back() <= i + num_iter) {
                --freq[i];
                ++freq[zeros.back()];
                zeros.pop_back();
            }
            if (freq[i] > 1) {
                freq[i + num_iter] += freq[i] - 1;
                freq[i] = 1;
            }
        }
        for (auto x : freq)
            if (x > k) return false;
        return true;
    };

    int bs = 0;
    for (int i = 1 << 20; i; i /= 2) {
        if (run(bs + i) == false) bs += i;
    }
    cout << bs + 1 << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
}

关于问题的思考

这是一个非常好的提问。当我们陷入代码细节（比如数组开多大、边界是 < 还是 <=）时，往往会迷失对题目本质的理解。

我们把代码放在一边，从头开始，用最通俗的语言重新拆解这个题目。

---

一、 题目到底在讲一个什么故事？

想象一条单行道（数轴），上面有很多无人机（车）。

每个位置 $i$ 表示能量值（坐标）。

核心规则：

1. 拥挤限制：任何一个坐标点上，最多只能停 $k$ 辆车。

2. 受迫移动：如果某个坐标点停了超过 $k$ 辆车，多出来的车必须同时向前开 1 格（能量 +1）。

3. 连锁反应：这可能会导致下一个格子也变拥挤，于是下一轮大家又要继续往前开。

问题：

这一场“交通疏导”需要多少轮才能结束？

（换句话说，所有车里，移动步数最多的那辆车，到底走了几步？）

---

二、 这个题目在考什么？

这道题考察了三个层面的能力：

1. 转化能力（Simulation $\to$ Optimization）：

   • 题目描述的是一个动态模拟过程（第一秒走一步，第二秒走一步...）。

   • 如果直接写模拟，时间复杂度不可控（可能会走几十万步）。

   • 你需要把它转化为一个静态规划问题：“如果我限制每辆车最多只能走 $x$ 步，能不能把它们塞进合法的坑位里？”

2. 二分答案（Binary Search on Answer）：

   • 显然，如果允许走 100 步能停好，那允许走 101 步肯定也能停好（单调性）。

   • 所以我们可以猜答案 $x$，然后验证可行性。

3. 贪心构造（Greedy Strategy）：

   • 这是最难的一点。在验证“$x$ 步是否够用”时，我们需要一种策略来安排车的位置。

   • 这里有两种流派，导致了你的困惑：

     • 流派 A（顺推）： 车子从左往右进场，有空位就占，占不到就报错。（这是我在上一个回复推荐的，最符合直觉）。

     • 流派 B（逆推/官方题解）： 这是一个非常数学化的技巧，试图把峰值“削平”填到谷底。你的代码和官方题解都是用的这个思路。

---

三、 为什么你的代码在 check(0) 时会逻辑自爆？

你一直纠结的 check(0) 特判，不是因为题目逻辑在 0 处特殊，而是因为你（和官方题解）采用的“逆推贪心算法”在实现上有一个 Bug。

让我们看着这几行代码：

C++

// 你的 check 函数片段
if(cnt[i] > 1){
    // 这里的逻辑是：把多余的移到 i+x 处
    cnt[i+x] += cnt[i]-1; 
    cnt[i] = 1; 
}

场景模拟：

假设位置 i=5 有 3 辆车 (cnt[5] = 3)。

现在我们二分猜测 $x=0$（即不允许移动）。

正常逻辑：

车子不能动。位置 5 有 3 个，如果 $k=2$，那肯定不合法，check 应该返回 false。

你的代码逻辑：

1. cnt[i] > 1 成立（3 > 1）。

2. cnt[i+x] 等于 cnt[5+0] 即 cnt[5]。

3. 代码执行：cnt[5] += cnt[5] - 1 $\to$ 3 + (3-1) = 5。

4. 代码执行：cnt[5] = 1。

5. 结果：cnt[5] 变成了 1。另外两辆车直接被代码“吃掉”了！

6. 最后检查 cnt[5] <= k，当然通过。

结论：

因为 x=0 时，源地址 i 和目的地址 i+x 是同一个变量。你的代码先修改它，然后又强制覆盖它，导致数据丢失。

这就是为什么必须特判 check0，或者让二分从 1 开始，避开这个逻辑陷阱。

---

四、 深入解析：那个“看不懂”的官方思路到底在干嘛？

你可能很疑惑：“为什么官方题解要从右往左？为什么它要用 >1 而不是 >k？”

这是一个“注水填坑”模型。

想象地势图，柱子高度是无人机数量。

官方思路是：如果不考虑 $k$ 的限制，我能不能把所有柱子的高度都削成 1？（极致的平铺）。

1. 从右往左扫：因为车子只能往右开（变大）。我们站在右边，看着左边的车过来。

2. zeros 栈：这是记录“低洼地带”（空坑）。

3. 核心操作：

   • 发现左边有个高柱子 i (cnt > 1)。

   • 看看右边最近的低洼地 s.back()。

   • 如果在射程 x 内，就把柱子削短，填到低洼地里。

   • 如果射程内没低洼地，就把多余的扔到射程极限 i+x 处堆起来。

4. 最后审判：

   • 虽然过程中我只保证了“尽量削成 1”，没有管 $k$。

   • 但如果我把多余的都扔到了极限位置后，只要最终所有位置的高度都不超过 $k$，那就成功了。

为什么这个思路容易写错？

• 因为它把 $k$ 的限制后置了。

• 它对“空位”的定义很狭隘（必须是 0 才是空位，其实对于 $k=3$，只有 1 个车的位置也是空位，但这个算法忽略了）。

• 它极其依赖数组边界和覆盖逻辑（正如你遇到的 cnt[i+x] 越界和覆盖问题）。

---

五、 总结与建议

这个题目在考什么？

考你能不能跳出“一步步模拟”的思维陷阱，转而用“二分 + 目标状态判定”来解决问题。

给你的最终建议：

虽然你已经修复了官方思路的代码（通过特判0、开大数组），但我强烈建议你忘掉官方那个从右往左的思路。

下次遇到这种“单向移动 + 容量限制”的题，请使用“交通堵塞（从左往右）”模型：

1. 把所有人按初始位置排序。

2. 维护一个指针 now（当前能停的最早位置）。

3. 遍历每个人：

   • 如果他想去的位置比 now 还大，那就更新 now。

   • 如果 now 超过了他的最大步数限制，直接 return false（堵死了）。

   • 安排他在 now，计数器 +1。

   • 如果 now 满了 $k$ 个，now++。

这个思路：

• 不需要特判 0。

• 不需要把数组开到 8 倍。

• 不需要脑补“削峰填谷”。

• 完全符合物理直觉。

关于题目为啥check函数这么写

这是一个非常深刻的问题！这触及到了贪心算法（Greedy）和网络流/动态规划之间最核心的区别。

你的直觉是完全正确的：在物理世界（或者最小化最大值的优化问题）里，“平均分配”通常是最优解。

但是，在这个特定的题目验证逻辑（Check函数）中，“堆在极限位置”（即把多余的直接扔到 $i+x$）之所以成立，是因为一个极其隐蔽的“等价性原理”。

我用一个生活化的例子来为你揭示为什么“堆在最后”和“平均分配”在这里是等价的，甚至前者更好算。

---

1. 核心逻辑：多米诺骨牌效应（Chain Reaction）

假设 $k=1$（每个位置只能停1辆车）。

此时我们在位置 $i$ 有 3 辆车。

允许的最大步数是 $x=2$。

你的直觉（平均分配）：

你觉得应该把多出来的 2 辆车，分别放到 $i+1$ 和 $i+2$。

这样大家都不挤，对吧？

但是，如果 $i+1$ 和 $i+2$ 已经有车了呢？

• 位置 $i$：有 3 辆车（多 2 辆）。

• 位置 $i+1$：原有 1 辆车。

• 位置 $i+2$：原有 1 辆车。

如果你把 $i$ 的多余车辆移动到 $i+1$：

1. $i$ 的车到了 $i+1$，导致 $i+1$ 变成了 2 辆（超载）。

2. $i+1$ 原有的那辆车被迫继续往后动，去 $i+2$。

3. $i+2$ 变成 2 辆（超载），原有的车被迫去 $i+3$……

结论：

把车从 $i$ 移到 $i+1$，如果 $i+1$ 是满的，就等价于把 $i+1$ 的车挤到了 $i+2$。

这就像推多米诺骨牌：你在 $i$ 推一下，力量会一直传递下去。

与其计算“$i$ 挤 $i+1$，然后 $i+1$ 挤 $i+2$”，不如直接把 $i$ 的车“瞬移”到它能到达的极限 $i+x$。

因为中间的每一个位置，如果它是满的，它自己会负责把它的车往后推。

---

2. 为什么要“留白”？（Reservation Principle）

这是理解这个算法最重要的视角：把路留给别人走。

假设我们从左往右处理（遍历 $i, i+1, \dots$）。当我们站在 $i$ 的时候：

• 只有我们知道 $i$ 的车最多能走到 $i+x$。

• $i+1$ 的车还没开始处理，它最多能走到 $i+1+x$。

如果你把 $i$ 的车停在 $i+1$（平均分配）：

你占用了 $i+1$ 的宝贵名额。等轮到处理 $i+1$ 的时候，它发现自己的位置被前面的 $i$ 占了，它就不得不往后跑得更远。

如果你把 $i$ 的车直接扔到 $i+x$（堆在极限）：

你把 $i+1, i+2, \dots, i+x-1$ 这些中间地带全部空出来。

这样，$i+1$ 的车就可以舒舒服服地停在 $i+1$（或者它射程内的任何地方），而不会被 $i$ 挤走。

贪心策略的核心：

既然 $i$ 的车能力最差（射程终点 $i+x$ 最小），而 $i+1$ 的车射程更远（终点 $i+1+x$），那么应该让 $i$ 尽早落地（或者去它的极限），尽量不要去干扰 $i+1$ 的生存空间。

但在这个题的逻辑里，其实是反过来的：把困难留给未来。

把 $i$ 的多余负载扔给 $i+x$，是因为我们在 $i$ 的时候，根本不想管 $i+1 \dots i+x$ 的死活，我们假设中间的节点如果自己满了，它们自己会往后扔。

我们只负责把 $i$ 的问题解决掉。既然 $i$ 的车只要在 $i+x$ 之前落地都算合法，那我就把它扔到最远，最大程度地减少对“近邻”的干扰。

---

3. 为什么“堆在最后”不会导致最后爆掉？

你担心的点是：“如果我把多余的都堆在 $i+x$，那 $i+x$ 岂不是会堆得比山还高？超过 $k$ 怎么办？”

答案是：会处理的，但不是现在。

当循环（遍历）从 $i$ 走到 $i+x$ 的时候：

1. 我们会发现 $i+x$ 这里堆了很多车（有原有的，也有之前从 $i$ 扔过来的）。

2. 此时我们再对 $i+x$ 进行同样的判断：只要 $i+x$ 这里的车，能在它的射程 $(i+x) + x$ 之内找到位置放下，那就是合法的。

3. 于是，$i+x$ 会再次把多余的车扔到 $i+2x$。

只要能在数组尽头之前把车通过这种“接力”的方式疏散完，方案就是可行的。

---

4. 总结：平均 vs 堆叠

• 平均分配（你的直觉）：

  • 试图让局部看起来平整。

  • 代码极难写：你需要遍历 $i+1$ 到 $i+x$，一个个填坑。时间复杂度会爆炸（从 $O(n)$ 变成 $O(n \cdot x)$）。

• 堆在极限（代码做法）：

  • 利用了连通性/传递性。

  • 既然 $A$ 占了 $B$ 的位子会导致 $B$ 往后移，那不如 $A$ 直接往后移。

  • 代码只需 $O(1)$：cnt[i+x] += excess。

  • 这是一种“懒惰计算”：我现在不处理细节，把多余的量扔到我的能力边界，等我遍历到那个边界时，再来处理这些量。

所以，不是你的直觉错了，而是为了代码实现的效率（避免循环填坑），我们利用数学上的等价性，选择了“堆在极限”这种写法。它在效果上等同于“最极端的推挤”，如果连这种极端推挤都能被后续消化，那平均分配肯定也能被消化。

关于直觉的培养

这是一个非常棒的复盘时刻。这道题其实是竞技编程（Competitive Programming）中一道非常经典的“分水岭”题目。

它考察的不是某种生僻的数据结构（如线段树、平衡树），而是考察你建立模型和简化问题的能力。

以下我为你总结这道题的核心考点，以及以后遇到这类题目的思维框架。

---

一、 这道题到底在考什么？（核心考点）

这道题剥去“无人机”和“能量”的外壳，本质是在考三个东西：

1. 二分答案（Binary Search on Answer）—— 转化问题的能力

• 特征：题目问“最少需要多少次操作”、“最小的最大值”、“最大的最小值”。

• 考点：你能不能敏锐地发现答案具有单调性？

  • 如果允许走 100 步能成功，那允许走 101 步一定也能成功。

  • 一旦发现单调性，立刻要把“求最优解（Optimization）”转化为“判定性问题（Feasibility）”。

  • 思维转变：不再想“怎么走最优”，而是想“如果规定只能走 $X$ 步，能不能走通？”

2. 贪心验证（Greedy Check）—— 化繁为简的能力

• 特征：在 check(x) 函数里，如何判断可行性？

• 考点：你能不能克服“物理模拟”的诱惑？

  • 初级思维：我要模拟每一步怎么走，我要平均分配，我要照顾每个点。（也就是你之前的“平均”思路）。

  • 高级思维：利用等价性（上一条回复提到的）。我不关心中间过程怎么走，我只关心“把包袱甩给极限位置”后，系统会不会崩。

  • 这是一种“延迟决策”的思想：现在的麻烦，能在截止日期（$i+x$）前解决就行，不用现在立马解决。

3. 差分/前缀和思想的变体 —— 流（Flow）的思想

• 考点：把数组看作水流。

• 位置 $i$ 多出来的东西，流向 $i+1$。如果把 $i$ 直接扔到 $i+x$，其实相当于把这一段的“流动压力”瞬间传递过去了。

---

二、 以后遇到这种题如何思考？（思维导图）

当你看到题目描述是：“一堆东西要移动/分配，有一些限制，问最小代价/最大容量”时，请按以下步骤思考：

第一步：能不能二分？

• 问自己：如果我知道答案是 $X$，判断“可行性”是否容易？

• 如果判定比求解容易，无脑上二分。

第二步：设计 Check 函数（核心中的核心）

在 check(mid) 里，不要去模拟题目说的“每秒发生什么”。要用上帝视角安排位置。

黄金法则：

1. 方向性：是从左往右扫，还是从右往左扫？

   • 通常顺着移动方向扫比较简单（例如车只能向右，那就从左往右扫）。

2. 贪心策略：

   • 当前位置 $i$ 的任务：必须处理掉，否则就没机会了（因为是从左往右扫，过了 $i$ 就回不来了）。

   • 处理方式：尽最大努力向后“甩锅”。

     • 如果你有多余的量：扔到最远合法的坑（$i+mid$）。为什么？因为这样给中间留出的空位最多。

     • 如果你缺量（比如某些题要求每个位置必须有车）：从最近合法的坑拉过来。

第三步：警惕边界

• 是否越界？（你的 $i+x$ 可能会超过 $N$）。

• 是否需要开大数组？（通常这种向后推的题，数组要开到 $N + \text{max\_step}$）。

---

三、 举一反三：类似题目的一通百通

为了让你彻底掌握，我举几个常见的类似模型（你可以去 Codeforces 或 LeetCode 找类似的题）：

模型 1：任务截止日期（Deadline）

题目：你有 $N$ 个任务，每个任务要在 $D_i$ 天前完成，耗时 $T_i$。问能不能做完？或者问最小的单位处理速度？

思考：

• 这就是典型的“向后推”贪心。

• 按截止日期排序。

• 当前任务做不完？把剩余的工作量推到下一天。

• Check 逻辑：如果在某一天，堆积的工作量超过了这一天到最终截止日期的总容量，就 return false。这和无人机的“堆在 $i+x$”是一模一样的道理。

模型 2：青蛙跳荷叶 / 覆盖问题

题目：数轴上有几个坑，你有几个木板，木板长度为 $L$，问最少几块木板能盖住所有坑？或者木板长度最少要是多少？

思考：

• 二分长度 $L$。

• Check 逻辑：从左往右扫，遇到第一个坑，贪心地把木板的左端点对齐这个坑（或者让木板尽可能往右延伸）。

• 这也是“最大化当前操作的价值”，和无人机“尽可能往后飞”是同构的。

模型 3：平整路面（CF 常见题）

题目：给你一堆土堆，你可以把土从 $i$ 移到 $i+1$（花费 1），问把所有土堆高度变一样，最小花费？

思考：

• 这就是一种“流”的模型。

• $i$ 多出来的土，必须给 $i+1$（因为 $i$ 只能和 $i+1$ 交互）。

• 如果在 $i$ 处堆积了 $S$ 的土，它对答案的贡献就是 $|S|$（因为这 $S$ 的土至少要流过 $i$ 到 $i+1$ 这段路）。

---

四、 总结你的“顿悟时刻”

你之前纠结的“平均分配” vs “堆在最后”，其实是“构造解” vs “验证解” 的区别。

• 如果题目让你打印最终每架无人机的位置，那你可能需要考虑“平均分配”，让输出好看点。

• 但题目只问“行不行”（或者“最小次数”），那么怎么极端怎么来。只要数学上不爆，就按最懒的方式写。

下一题 Next Step：

你可以尝试去做一下 LeetCode 410. Split Array Largest Sum (分割数组的最大值) 或者 Codeforces 1200-1400 分段关于“Binary Search on Answer”的题单。用今天这个“二分+贪心验证”的套路去套，你会发现它们长得都一样。