思路。最后一步只有三种：最后一束是 AAA（用了末三朵、且它们都是 0）、是 AB（用了末两朵、一 A 一 B，顺序不限）、或者末尾若干朵花根本不进任何花束。设 \(dp_i\) 为「只用前 \(i\) 朵花」能取得的最大价值，转移即为三者取最大：

方括号指示项不满足条件时取 \(-\infty\)（不合法）。关键在于「不扎」这一支保证了花可以剩下不用，且扎花的花必须相邻这一约束被「末 k 朵整体成束」编码进状态截断里。手算 \(f = [0,0,0,0,1]\)、\(p=10\)、\(q=6\)：\(dp_3 = 10\)（前三朵扎 AAA），\(dp_5 = \max(dp_4, dp_3 + q) = 16\)——前三朵扎 AAA、第四五朵（A、B 相邻）扎 AB，组合优于任何单一方案。

代码。

long long maxBouquetValue(const vector<int>& f, long long p, long long q) {
    int n = (int)f.size();
    vector<long long> dp(n + 1, 0);           // dp[i]：只用前 i 朵花的最大收益
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1];                     // 第 i 朵不进任何花束
        if (i >= 3 && !f[i-1] && !f[i-2] && !f[i-3])
            dp[i] = max(dp[i], dp[i - 3] + p); // 末三朵 0,0,0 扎 AAA
        bool ab = (f[i-1] == 0 && f[i-2] == 1) || (f[i-1] == 1 && f[i-2] == 0);
        if (i >= 2 && ab)
            dp[i] = max(dp[i], dp[i - 2] + q); // 末两朵一 A 一 B 扎 AB
    }
    return dp[n];
}

复杂度。时间 \(O(n)\)，空间 \(O(n)\)（只需最近三个值，可滚动到 \(O(1)\)）。

边界。\(n \lt 2\) 时无法扎任何花束，返回 0；AB 是否区分顺序（A 在前还是 B 在前）建议向面试官确认，本实现两种都允许；p、q 可为 0 或负（亏本的花束不扎，dp 自然处理）。

面试怎么讲。先把「最后一步」说出来：最后一束花要么 AAA、要么 AB、要么末尾的花不用。这一句就是状态设计的全部；剩下的转移只是机械展开。追问「能不能输出扎法」时，在 dp 上记录每步的选择再回溯即可。

思路（建模是本题主角）。把第 \(i\) 列硬币的高度记为 \(h_i\)。水滴落下后，位置 \(i\) 处的水位不会超过「左侧最高硬币」与「右侧最高硬币」的较小者，因为超过就会从矮的一侧溢出。于是每列能稳定停留的水滴数为

总滴数即 \(\sum_i d_i\)。源题的「能存 2 滴」对应最小非平凡例子：高度 \([2, 0, 2]\)，中间列水位被两侧夹到 2，存 \(2 - 0 = 2\) 滴。\(L\) 与 \(R\) 各一次线性扫描即可预计算，这正是「前缀最值 + 后缀最值」的 DP。

代码。

long long totalDrops(const vector<int>& h) {  // h[i]：第 i 列硬币叠放的高度
    int n = (int)h.size();
    if (n == 0) return 0;
    vector<int> L(n), R(n);                    // 左/右两侧（含自身）最高的一列
    L[0] = h[0];
    for (int i = 1; i < n; ++i) L[i] = max(L[i-1], h[i]);
    R[n-1] = h[n-1];
    for (int i = n - 2; i >= 0; --i) R[i] = max(R[i+1], h[i]);
    long long total = 0;
    for (int i = 0; i < n; ++i)
        total += max(0, min(L[i], R[i]) - h[i]);   // 水位由两侧较矮者决定
    return total;
}

复杂度。时间 \(O(n)\)（三次线性扫描），空间 \(O(n)\)。

边界。单调不降或单调不增的高度数组存不了水（每列 \(\min(L_i,R_i) = h_i\)）；\(n \le 2\) 必然为 0；高度为 0 的「空列」也照样参与计算——它只是矮墙。这道题与源题库另一道「接雨水」（海拔图存水）是同一模型的不同皮，后者还有双指针 \(O(1)\) 空间解法，完整推导放在 033. 编程三：滑动窗口与前缀和的例题里。

面试怎么讲。先用「两侧较矮者决定水位」这句物理直觉立住公式，再说明为什么逐列求和是安全的（每列独立）。主动提接雨水变体与双指针优化，是漂亮的收尾。

思路。最后一步分类：从第 \(n-1\) 阶跨 1、从第 \(n-2\) 阶跨 2、从第 \(n-3\) 阶跨 3，互斥完备，得 tribonacci 递推（见知识讲解）。斐波那契正是「只允许跨 1 或 2 阶」的特例。复杂度问题的标准答案：朴素递归是指数级（斐波那契约 \(O(1.618^n)\)，因为递归树每层近似分裂成两个子问题）；递推填表是 \(O(n)\) 时间；只依赖前三个状态，空间滚动到 \(O(1)\)；若 n 极大还要取模并用矩阵快速幂 \(O(\log n)\)。

代码。

long long countWays(int n) {                  // f(n) = f(n-1) + f(n-2) + f(n-3)
    if (n <= 1) return 1;                     // 0 阶：站着不动，也是 1 种
    vector<long long> f(n + 1);
    f[0] = 1; f[1] = 1; f[2] = 2;             // 小情形直接给边界
    for (int i = 3; i <= n; ++i) f[i] = f[i-1] + f[i-2] + f[i-3];
    return f[n];
}

复杂度。\(O(n)\) 时间、\(O(n)\) 空间；滚动后 \(O(1)\) 空间。

边界。\(f_0 = 1\) 的口径（空走法算一种）要在写代码前说出口；\(f_2 = 2\)（1+1 或 2）。tribonacci 增长底约 1.839，\(n = 80\) 已接近 long long 上限，大 n 必须配取模。

面试怎么讲。「最后一步跨几阶」这句分类语言是全部内容；复杂度分析按「朴素递归 → 填表 → 滚动 → 矩阵幂」四档报出，展示你知道每档存在的理由，而不是背复杂度。

unsigned long long fibonacci(int n) {
    if (n < 0 || n > 93) throw invalid_argument("uint64 Fibonacci requires 0 <= n <= 93");
    if (n == 0) return 0;
    unsigned long long previous = 0, current = 1;
    for (int i = 1; i < n; ++i) {
        unsigned long long following = previous + current;
        previous = current;
        current = following;
    }
    return current;
}

思路（DP 版）。设 \(dp_i\) 为到达下标 \(i\) 的最少步数，\(dp_0 = 0\)。正向转移：每个 \(i\) 把它能跳到的所有 \(j\) 松弛 \(dp_j = \min(dp_j, dp_i + 1)\)。源题的写法 \(\min(dp_i, dp_{i+j} + 1)\) 是从右往左倒推的同一件事（从终点往回看）。\(O(n^2)\)，正确但慢。

思路（贪心版）。把「一跳之内能到的位置」看成一层：维护当前层的右边界 end 与下一层最远可达 farthest，遍历到层边界时步数加一并进入下一层。每层只需一遍扫描，总 \(O(n)\)。本质是 BFS 的分层思想，因为每步代价相同，最先铺满的一定步数最少。

代码（贪心）。

int minJumps(const vector<int>& arr) {        // 贪心：按「一跳能到的层」逐层扩张
    int n = (int)arr.size();
    int jumps = 0, end = 0, farthest = 0;
    for (int i = 0; i < n - 1; ++i) {
        farthest = max(farthest, i + arr[i]);
        if (i == end) {                        // 当前层的候选位置耗尽
            if (farthest <= i) return -1;      // 原地卡死，到不了终点
            ++jumps;                           // 跨入下一层
            end = farthest;
        }
    }
    return jumps;
}

手算 \([2, 3, 1, 1, 4]\)：i=0 时 farthest=2，触到层边界，jumps=1、end=2；i=1 时 farthest=max(2, 4)=4；i=2 触到 end，jumps=2、end=4；end 已越过终点，返回 2。

复杂度。DP 版 \(O(n^2)\) 时间、\(O(n)\) 空间；贪心版 \(O(n)\) 时间、\(O(1)\) 空间。

边界。首元素为 0 且 \(n \gt 1\) 时不可达（返回 −1 或按题意报错）；\(n = 1\) 起点即终点，0 步；\(arr_i\) 可能为 0，卡死检测（farthest 不再前进）必须要有。

面试怎么讲。先给 DP（对齐源题给的递推，说明等价），再主动升级到贪心并点破「同权边最短路 → BFS 分层」这个视角。能讲清贪心为什么对（每层是最少步数相同的位置集合）比背代码重要。

思路。「每段排序后拼接非降」当且仅当相邻两段之间，左段的最大值不超过右段的最小值（段内部排序解决，段之间靠这个条件）。于是位置 \(i\) 与 \(i+1\) 之间能切一刀，等价于 \(\max(a_1..a_i) \le \min(a_{i+1}..a_n)\)。从左到右维护前缀最大、从右到左维护后缀最小（即源题口径的「从右往左前缀 min」），一刀一刀数出来。对 \([3,2,1,4,6,5]\)：后缀最小数组为 \([1,1,1,4,5,5]\)，前缀最大扫描到下标 3 时为 4，检查 \(4 \le \min(6,5)=5\)，下标 3 与 4 之间可切；下标 2 与 3 之间 \(3 \le 4\) 也可切——自由切分下其实能切成 \([3,2,1]\)、\([4]\)、\([6,5]\) 三段。PDF示例宣称答案2，但按写出的自由切分规则最优为3；等长切段或最小段长限制可以产生2，不过这些限制原文没有给出，不能当成已知事实；这正好说明面试时先澄清切分约束的必要。

代码。

int maxParts(const vector<int>& a) {          // 自由切分口径下的最大段数
    int n = (int)a.size();
    if (n == 0) return 0;
    vector<int> sufMin(n);                     // 从右往左维护的后缀最小值
    sufMin[n-1] = a[n-1];
    for (int i = n - 2; i >= 0; --i) sufMin[i] = min(a[i], sufMin[i+1]);
    int parts = 1, preMax = a[0];
    for (int i = 0; i + 1 < n; ++i) {          // 考察 i 与 i+1 之间能否切一刀
        preMax = max(preMax, a[i]);
        if (preMax <= sufMin[i+1]) ++parts;     // 左段全部 <= 右段全部
    }
    return parts;
}

复杂度。时间 \(O(n)\)，空间 \(O(n)\)。

边界。已排序数组每处皆可切，答案是 n；严格递减数组只能整段，答案 1；等长口径下需要检查每个 n 的因子，复杂度变为 \(O(n \cdot d(n))\)。

面试怎么讲。把「相邻段 max ≤ min」这个充要条件先证出来（两个方向各一句），代码就是查每个切位。主动指出源题答案 2 与自由切分答案 3 的口径差，展示澄清习惯。

思路。0/1 背包可达性：设 \(\mathrm{reach}(s)\) 为「和 s 能否被凑出」，逐件物品决策「不拿」或「拿」。第 \(x\) 件物品加入后，所有 \(s - x\) 可达的和使 \(s\) 可达：

实现上用一维布尔数组、容量从大到小枚举（倒序保证每件物品只用一次——正序会允许同一件被拿多次，变成完全背包）。目标 0 恒可达（空子集）。

代码。

bool canReach(const vector<int>& items, long long target) {  // 0/1 背包可达性
    if (target < 0) return false;
    vector<char> reach(target + 1, 0);
    reach[0] = 1;                              // 空子集的和为 0
    for (int x : items)
        for (long long s = target; s >= x; --s)   // 倒序：每件物品至多用一次
            if (reach[s - x]) reach[s] = 1;
    return reach[target];
}

复杂度。时间 \(O(n \cdot T)\)、空间 \(O(T)\)，\(T\) 为目标值——这是伪多项式（pseudo-polynomial）：复杂度对目标值的数值线性、对输入比特数是指数级。用 bitset 可把时间除以机器位宽 64。

边界。默认元素非负；若允许负数，可达和不再是 \([0, T]\) 的区间，改用有序集合维护可达和。target 为 0 返回 true；元素可重复出现但每件仍只用一次。

面试怎么讲。先声明「这是子集和问题，0/1 背包的判定版，伪多项式可解、一般化的维度下是 NP 完全的判定问题」——一句话定位问题的难度坐标，然后给 DP。倒序枚举的原因务必能讲清。

bool canReachIntegers(const vector<int>& items, long long target) {
    unordered_set<long long> reachable{0};
    for (int x : items) {
        vector<long long> additions;
        additions.reserve(reachable.size());
        for (long long sum : reachable) additions.push_back(sum + x);
        reachable.insert(additions.begin(), additions.end());
    }
    return reachable.count(target) != 0;
}

题面与方法。PDF没有限制每天最多两部，因此这是容量为3小时的装箱问题。将时长精确换成整数分钟（有限小数可统一到更细单位），每天容量180。小规模用分支限界得到精确最优：先按时长降序，逐部尝试放进每个装得下的已有天，或新开一天。相同已用时长的天是对称状态，只尝试一个。每一种合法排片都在这个搜索树中；当前天数已不小于最好答案时可以剪枝，因为后续不会减少已开天数。

int minDaysMinutesExact(vector<int> minutes, int capacity = 180) {
    if (capacity <= 0) throw invalid_argument("positive daily capacity required");
    for (int length : minutes) {
        if (length <= 0) throw invalid_argument("movie duration must be positive");
        if (length > capacity) return -1;
    }
    if (minutes.empty()) return 0;
    sort(minutes.rbegin(), minutes.rend());
    int best = minutes.size();
    vector<int> used;
    function<void(int)> search = [&](int i) {
        if ((int)used.size() >= best) return;
        if (i == (int)minutes.size()) { best = used.size(); return; }
        set<int> triedLoads;
        for (int day = 0; day < (int)used.size(); ++day) {
            if (minutes[i] > capacity - used[day] || !triedLoads.insert(used[day]).second)
                continue;
            used[day] += minutes[i];
            search(i + 1);
            used[day] -= minutes[i];
        }
        used.push_back(minutes[i]);
        search(i + 1);
        used.pop_back();
    };
    search(0);
    return best;
}

核验。[60,60,60,60,60]可分成3部和2部，两天完成；“每天至多两部”的双指针会错误给三天。[120,120,120]总时长360、容量下界2天，但任意两部不能同日，实际三天。因此\(\lceil\text{总时长}/180\rceil\)只是下界。

规模与条件。一般装箱是NP难问题，此精确搜索最坏指数级（粗上界O(nⁿ)），排序O(n log n)，负载数组与递归栈为O(n)，各层对称去重集合合计最坏O(n²)额外空间；应对照输入规模选用。大规模可用首次适应递减FFD近似，必须标记不保证最优；“每天至多两部”的排序双指针是另一道受限题，不能冒充本题。任何单片超过容量返回−1，空列表返回0。

思路。连续的空闲位置构成一段空隙；两个被占位置之间的空隙互不影响，可以各自填充。关键观察是：长度为 \(L\) 的空隙恰好能被 \(2\) 的幂铺满，且最省文件数的方案唯一——就是 \(L\) 的二进制分解。从大到小贪心（先放 \(2^{\lfloor \log_2 L \rfloor}\)，再递归余量）与二进制分解等价，因为每个 \(2^k\) 至多用一次（用了两次该幂就应合并成 \(2^{k+1}\)），而任何小于等于 \(L\) 的幂集合若要不重复地恰好凑出 \(L\)，只能是二进制表示里那些位。于是答案 = 各空隙长度的二进制中 1 的个数之和（popcount）。

代码。

long long countFiles(const string& slot) {    // '#' 已占用，'.' 空闲
    long long files = 0, run = 0;              // run：当前连续空隙长度
    for (char c : slot) {
        if (c == '.') ++run;
        else { files += __builtin_popcountll(run); run = 0; }
    }
    files += __builtin_popcountll(run);        // 收尾的空隙别漏
    return files;
}

例如 "#..##...#"：两段空隙长度 2 与 3，分别需要 \(2\)、\(2+1\) 个文件，共 3 个。

复杂度。时间 \(O(n)\)，空间 \(O(1)\)。

边界。全占用返回 0；长度 0 的空隙 popcount 为 0 自动跳过；若空隙极长，popcount 用 64 位内建函数即可，或按位循环统计。

面试怎么讲。把「贪心从大到小」与「二进制分解唯一性」的等价说清楚是核心得分点；位运算（popcount）只是把结论翻译成代码。

思路。设 \(dp_{i,j}\) 为「以 \((i,j)\) 为右下角的最大全 1 正方形边长」。若 \(g_{i,j} = 1\)，这个正方形向左上三个方向同时受限，转移为三邻取最小再加一：

怎么读：边长为 \(d\) 的正方形以 \((i,j)\) 为右下角，等价于它的左边一格、上边一格、左上一格分别能撑起边长至少 \(d-1\) 的正方形；三者取最小就是瓶颈。答案是所有 \(dp_{i,j}\) 的最大值的平方。状态定义里的「右下角」与 Kadane 的「以 i 结尾」是同一种定语技术：让全局最优可枚举。

代码。

int maximalSquareArea(const vector<vector<int>>& g) {   // 返回全 1 最大正方形面积
    int m = (int)g.size(), n = (int)g[0].size(), best = 0;
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (g[i][j] == 1) {
                if (i == 0 || j == 0) dp[i][j] = 1;          // 边界：只能自成一格
                else dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                best = max(best, dp[i][j]);
            }
    return best * best;
}

复杂度。时间 \(O(mn)\)，空间 \(O(mn)\)，滚动一行后 \(O(n)\)。

边界。全 0 矩阵返回 0；单行单列时最大正方形至多边长 1；矩阵为空直接返回 0。追问「最大全 1 矩形（不是正方形）」时需要单调栈按行处理直方图，复杂度同为 \(O(mn)\)，可作为延伸提一句。

面试怎么讲。先画图说明三邻取 min 的含义（木桶效应），再给转移。被问「为什么不是 max+1」时，用反例回应：右上方向的空缺无法被三个邻居中任何一个看到。

思路。先算清一次交换的收益：交换相邻位置 \(i\) 与 \(i+1\)（权重 \(i+1\) 与 \(i+2\)），目标函数变化

即交换「降序对」（\(a \gt b\)）才有正收益——直觉上要让大数尽快拿到大权重，这与「整体排序后最大」一致。若题意是「总共至多交换一次」，答案就是 \(\max(0, \max_i (Arr_i - Arr_{i+1}))\) 加上原加权和。更常考的口径是每个元素至多参与一次交换：交换两两不相交，各对收益独立可加，问题变成「选出收益和最大的不相邻对」，即打家劫舍式的一维 DP：

手算 \([3,1,2,5,4]\)：各对收益 \(2, -1, -3, 1\)，选 \((3,1)\) 与 \((5,4)\) 两个不相交对，总增益 3；原加权和 \(51\)，优化后 \(54\)。

代码。

long long maxWeightedSum(vector<int> a) {      // 口径：每个元素至多交换一次
    int n = (int)a.size();
    long long base = 0;
    for (int i = 0; i < n; ++i) base += (long long)a[i] * (i + 1);
    if (n < 2) return base;
    vector<long long> g(n, 0);                  // g[i]：只考虑前 i+1 个位置的最大增益
    for (int i = 1; i < n; ++i) {
        long long gain = max(0LL, (long long)a[i-1] - a[i]);  // 交换 (i-1,i) 的收益
        g[i] = g[i-1];                         // 不动这一对
        if (i >= 2) g[i] = max(g[i], g[i-2] + gain);
        else g[i] = max(g[i], gain);
    }
    return base + g[n-1];
}

复杂度。时间 \(O(n)\)，空间可滚动到 \(O(1)\)。

边界。n 小于 2 无交换可言；所有相邻对都升序时增益为 0。面试第一句话应当是澄清「至多一次」是总共一次还是每个元素一次——两种口径答案不同，前者平凡、后者才需要 DP。

面试怎么讲。先推 \(\Delta = a - b\) 这一步初等代数（展示不慌），再指出「不相交交换 → 不相邻选择 → 打家劫舍模板」这条归约链。模板识别能力正是这类题的考点。

原题无法唯一求解。PDF没有定义操作，不能直接给一个确定答案。例如[5]操作一次，减1得4、向下折半得2、向上折半得3。以下只是两个明确标注的补充模型，不声称还原了原题未写出的规则。

非负整数折半模型。向下折半的节省为\(x-\lfloor x/2\rfloor=\lceil x/2\rceil\)；向上折半的节省为\(x-\lceil x/2\rceil=\lfloor x/2\rfloor\)。每个元素反复折半的边际节省单调不增，因此每步选择当前最大节省是最优；两种模型的节省都随当前值非减，可用最大堆按当前值选取。roundUp=false对应向下取整，true对应向上取整。

long long minSumAfterOps(const vector<long long>& a, long long k, bool roundUp = false) {
    if (k < 0) throw invalid_argument("k must be nonnegative");
    priority_queue<long long> pq;
    long long total = 0;
    for (long long x : a) {
        if (x < 0) throw invalid_argument("halving model requires nonnegative entries");
        pq.push(x); total += x;
    }
    if (pq.empty() && k > 0) throw invalid_argument("no entry to operate on");
    while (k-- > 0 && !pq.empty()) {
        long long x = pq.top(); pq.pop();
        long long y = x / 2 + (roundUp && x % 2);
        if (x == y) break;  // Remaining operations cannot improve the sum.
        total -= x - y;
        pq.push(y);
    }
    return total;
}

O(n log n+k log n)时间、O(n)空间；提前进入全无收益状态时，剩余操作可以在0或1等不变元素上消耗。例[5]、k=1，两种开关分别返回2与3。总和须在long long范围。若真实操作不是折半，必须重新设计状态/转移，不能沿用这个堆作为“原题答案”。

先说明优化目标。原文只问k次后有多少不同值，未明确最大化；若不指定策略，结果依赖具体交换。以下解最大化版本，允许任意跨数组下标、重复使用下标，也允许相同值交换。下标按0…n−1理解。

设A原有b种值、重复占位d=n−b，B里A没有的新值有f种。一交换最多增加一种值，且必须用A里的重复副本换入新值；因此上界是\(b+\min(k,d,f)\)。不断做这种交换即可达到。

恰好k次也能达到该式。若有多余次数：当A仍有重复但B已无新值，可在两数组中选同值交换；当A全是不同值，B有同值则交换同值，否则用任一B新值替掉A任一旧值，不改变种类数。因此在当前允许的操作下，总能消耗额外次数且不降目标，不能宣称“恰好多次必然变差”。

int maxDistinctAfterK(const vector<int>& A, const vector<int>& B, int k) {
    if (A.size() != B.size() || k < 0) throw invalid_argument("equal lengths, nonnegative k required");
    if (A.empty() && k > 0) throw invalid_argument("no elements to swap");
    unordered_set<int> sa(A.begin(), A.end()), sb(B.begin(), B.end());
    int fresh = 0;
    for (int value : sb) if (!sa.count(value)) ++fresh;
    return (int)sa.size() + min({k, (int)A.size() - (int)sa.size(), fresh});
}

例A=[1,1]、B=[2,2]、k=2：先把A₀=1与B₀=2交换，得A=[2,1]、B=[1,2]；再交换A₀与B₁，两者同为2，最终仍有两种值。若禁止同值交换、限制每个下标只能用一次或规定i=j，就不再是此题的操作集合，须另解。哈希平均O(n)时间、O(n)空间。

PDF未要求连续切分。应区分“从某处切成前后段”和“任意把元素分进两个组、组内保留原顺序”。前者枚举前缀长度m，检查\(2m\lt n\)和\(P_m\gt S-P_m\)，O(n)。后者并非一般子集和判定：只要求和超过另一组，没有指定精确目标；固定大小m的最大和就是最大的m个元素之和。因此按值降序，枚举\(1\le m\lt n/2\)即可，O(n log n)。这种论证对带负数的输入也成立。

int splitShortGreaterPrefix(const vector<long long>& a) {
    long long total = accumulate(a.begin(), a.end(), 0LL), prefix = 0;
    for (int length = 1; 2LL * length < (long long)a.size(); ++length) {
        prefix += a[length - 1];
        if (prefix > total - prefix) return length;
    }
    return -1;
}

vector<int> shorterGreaterSubset(const vector<long long>& a) {
    vector<pair<long long, int>> order;
    for (int i = 0; i < (int)a.size(); ++i) order.push_back({a[i], i});
    sort(order.rbegin(), order.rend());
    long long total = accumulate(a.begin(), a.end(), 0LL), sum = 0;
    for (int length = 1; 2LL * length < (long long)a.size(); ++length) {
        sum += order[length - 1].first;
        if (sum > total - sum) {
            vector<int> indices;
            for (int j = 0; j < length; ++j) indices.push_back(order[j].second);
            sort(indices.begin(), indices.end());
            return indices;
        }
    }
    return {};  // No nonempty shorter group works.
}

第二个函数返回所选元素的原下标，按下标递增保证组内原顺序；其余元素构成第二组。例[1,9,1]：没有合法的更短且更大和的前缀，但任意分组可选中间的9，对其余[1,1]。两组非空、长度严格不等；n≤2不存在第一组更短的非空二分。各总和假定不溢出long long。