第 15 章 贪心 · 知识细节练习

判断题：贪心 = 每一步都做"当前看起来最好"的选择（局部最优），希望由此得到全局最优解。

判断题：局部最优不一定是全局最优——贪心对有些问题给正确答案，对另一些问题给错误答案，必须具体问题具体分析。

判断题：若一个问题具有贪心选择性质，则每一步的贪心选择都能通向全局最优解。

判断题：最优子结构 = 问题的最优解包含其子问题的最优解——贪心与动态规划都需要这个性质。

单选题：与枚举、动态规划相比，贪心的典型特征是？

判断题：验证贪心是否成立的最快方法是构造反例；找不到反例不等于证明正确，但竞赛中常用"小数据对拍 + 找反例"来检验。

判断题：人民币硬币面额（1、5、10、20、50、100 元）下，"每次取不超过剩余金额的最大面额"的找零贪心能得到最少张数——因为大面额都是小面额的倍数。

单选题：活动安排问题（每个活动有开始、结束时间，选最多个互不重叠的活动），正确的贪心策略是？

单选题：$n$ 个人排队接水、每人用时不同，要使总等待时间最小，接水顺序应该是？

单选题：物品可以分割的背包问题（部分背包），贪心策略是？

判断题：合并果子（每次合并两堆、代价为两堆之和，求最小总代价）：每次合并当前最小的两堆——本质是构建哈夫曼树。

判断题：均分纸牌：从左到右扫描，把每堆与平均值的差"传递"给下一堆，移动次数 = 差值不为 0 的堆数。

单选题：删数问题（删掉 $k$ 个数字使剩下的数最小），贪心策略是？

判断题：选最多不相交区间：按右端点升序排序，依次选"开始时间 $\geq$ 上一个选中区间右端点"的区间——该贪心正确。

单选题：用最少的点覆盖所有区间（每个区间至少含一个点），贪心策略是？

单选题：用最少的区间覆盖给定线段 $[L, R]$，贪心策略是？

单选题：安排所有活动所需的最少教室数，正确做法是？

判断题：区间分组（把区间分成最少的组、组内互不重叠）= 最少教室问题，解法完全相同。

判断题：大多数贪心先排序（按某种键）再扫描——排序是贪心的标准预处理步骤。

判断题：区间类贪心套路：明确排序键（左端点或右端点）→ 扫描维护当前状态 → 每步做贪心选择。

判断题：先排序再贪心是常见套路——区间安排、排队接水、部分背包都遵循它。

判断题：每次取当前最大或最小（如合并果子取最小两堆、部分背包取最大单价）是贪心最常见的形态。

判断题：读贪心题先找"排序键"——题目的限制条件里通常藏着贪心的排序依据（活动按结束时间、背包按单位价值、排队按用时），找到排序键，贪心就成了一半。

判断题：证明贪心正确性的常用方法：交换论证——把最优解中与贪心不同的相邻选择交换，证明交换后不更差，从而最优解可改成贪心解。

判断题：拿不准贪心是否正确时，用枚举/暴力对拍验证：小数据下贪心结果与暴力求出的最优解一致，才敢把贪心用在大数据上。

单选题：典型贪心（排序 + 线性扫描）的时间复杂度是？

判断题：当"当前最优"与"后续最优"互相冲突（选了眼前好的会堵死后面的好选择）时，贪心容易失效。

判断题：动态规划尝试所有可能的选择、记录每个状态的最优；贪心每步只锁定一个选择——贪心更快，但只对具有贪心选择性质的问题正确。

单选题：同样的问题枚举需要指数时间，若问题具有贪心性质，贪心通常只需？

判断题：分治把问题拆成独立的子问题分别解决再合并；贪心是顺序地做一连串局部选择——两者思路不同，少数问题（如哈夫曼树）两者都沾边。

判断题：回溯穷举所有可能（指数级但保证正确）；贪心只走一条路（快但可能错）——拿不准贪心是否成立时，小数据用回溯/枚举验证。

判断题：题目没有明显的贪心性质、且 $n$ 很小（如 $\leq 20$）时，别急着贪心——多半是枚举、回溯或动态规划。

单选题：物品不可分割的 0/1 背包为什么不能用"按单位价值贪心"？

判断题：贪心正确性证明的两块拼图：贪心选择性质（第一步选某个元素不亏）+ 最优子结构（选完后剩余子问题的最优解拼出全局最优）。

判断题：反证法：假设贪心解不是最优，则最优解的某一步与贪心选择不同，据此推出矛盾——贪心证明的常用骨架。

判断题：交换论证：把最优解中"与贪心不同的部分"逐步交换成贪心的选择，证明每次交换结果不更差。

判断题：数学归纳法也能证明贪心：归纳假设"前 $k$ 步贪心选择正确"，证明第 $k+1$ 步也正确。

判断题：一个反例就能否定贪心——贪心失效的判据是"找得到反例"。

判断题：数据范围 $n$ 很大（如 $10^5$、$10^6$）且"排序 + 线性扫描"可解，通常暗示贪心或排序贪心。

单选题：手电筒过河问题（$n$ 人过桥、速度不同、每次最多 2 人、手电筒必须送回），贪心策略是？

单选题：一条数轴上有若干点，要选一个点建仓库，使仓库到所有点的距离之和最小。贪心策略是？

判断题："每个区间至少种一棵树、求最少树数"就是区间选点问题：按右端点排序、每次选右端点。

判断题：两个窗口排队接水：贪心每次把下一个人分配给"当前累计时间更小（更早空闲）"的窗口。

判断题：把若干数字拼接成最小的数：不能按数值大小排序，要用拼接比较器（a + b < b + a）排序——如 3 和 32 应排成 323 而不是 332。

单选题：跳跃游戏（每个位置最多能向前跳 a[i] 步，判断能否到达终点）的贪心维护的是？

单选题："贪心只顾眼前最优、缺乏全局规划"的最典型后果是？

单选题：活动安排若按开始时间升序贪心，会？

单选题：找零贪心（每次取最大面额）成立的常见条件是？

判断题：合并果子 = 构建哈夫曼树：最小总合并代价 = 哈夫曼树的带权路径长度（WPL）。

判断题：以下结论全部正确——"贪心不一定对、需要贪心选择性质；区间调度按右端点排序；0/1 背包贪心会错、部分背包贪心正确；合并果子每次合并最小的两堆"。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int coins[4] = {25, 10, 5, 1};   // 美分面额（1 元 = 100 分）
05    int n = 4, money = 63, cnt = 0;
06    for (int i = 0; i < n; i++) {
07        cnt += money / coins[i];     // 尽量用当前最大面额
08        money %= coins[i];
09    }
10    cout << cnt;
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int coins[4] = {25, 10, 5, 1};
05    int money = 47;
06    for (int i = 0; i < 4; i++)
07        while (money >= coins[i]) {
08            cout << coins[i] << " ";   // 输出找出的每一枚硬币
09            money -= coins[i];
10        }
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {3, 1, 4, 1, 5, 9};
05    int k = 3, s = 0;                 // 选 3 个最大的数求和
06    for (int t = 0; t < k; t++) {
07        int p = t;
08        for (int i = t + 1; i < 6; i++)
09            if (a[i] > a[p]) p = i;   // 找当前最大的
10        swap(a[t], a[p]);
11        s += a[t];                    // 贪心：每次取最大
12    }
13    cout << s;
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {3, 1, 4, 1, 5, 9};
05    sort(a, a + 6, greater<int>());   // 降序排列
06    int s = 0;
07    for (int i = 0; i < 2; i++) s += a[i];   // 取前两个最大的
08    cout << s;
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {-2, 1, -3, 4, -1, 2};
05    int cur = 0, best = 0;
06    for (int i = 0; i < 6; i++) {
07        cur += a[i];
08        if (cur < 0) cur = 0;          // 贪心：和为负就重新开始
09        best = max(best, cur);
10    }
11    cout << best;                      // 最大子段和
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {1, 5, 2, 4, 3};
05    int l = 0, r = 4;
06    while (l <= r) {
07        if (a[l] < a[r]) { cout << a[l] << " "; l++; }  // 每次取两端较小者
08        else { cout << a[r] << " "; r--; }
09    }
10    return 0;
11}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int coins[3] = {25, 10, 1};
05    int money = 41, cnt = 0;
06    for (int i = 0; i < 3; i++) {
07        cnt += money / coins[i];
08        money %= coins[i];
09    }
10    cout << cnt;
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Act { int s, e; };              // 开始、结束时间
04int main() {
05    Act a[5] = {{1,4},{3,5},{0,6},{5,7},{3,8}};
06    sort(a, a + 5, [](Act x, Act y){ return x.e < y.e; });  // 按结束时间排序
07    int cnt = 0, last = -1;
08    for (int i = 0; i < 5; i++)
09        if (a[i].s >= last) { cnt++; last = a[i].e; }   // 能选就选
10    cout << cnt;
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Act { int id, s, e; };
04int main() {
05    Act a[5] = {{1,1,4},{2,3,5},{3,0,6},{4,5,7},{5,3,8}};
06    sort(a, a + 5, [](Act x, Act y){ return x.e < y.e; });
07    int last = -1;
08    for (int i = 0; i < 5; i++)
09        if (a[i].s >= last) { cout << a[i].id << " "; last = a[i].e; }
10    return 0;
11}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Seg { int l, r; };
04int main() {
05    Seg s[4] = {{1,3},{2,5},{4,6},{5,8}};
06    sort(s, s + 4, [](Seg x, Seg y){ return x.r < y.r; });
07    int cnt = 0, pos = -1;
08    for (int i = 0; i < 4; i++)
09        if (s[i].l > pos) { cnt++; pos = s[i].r; }  // 未覆盖就选右端点
10    cout << cnt;
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Seg { int l, r; };
04int main() {
05    Seg s[5] = {{0,3},{2,5},{4,7},{6,9},{8,10}};
06    sort(s, s + 5, [](Seg x, Seg y){ return x.l < y.l; });
07    int R = 10, cur = 0, cnt = 0, i = 0;
08    while (cur < R) {                            // 覆盖 [0, 10]
09        int far = cur;
10        while (i < 5 && s[i].l <= cur) { far = max(far, s[i].r); i++; }
11        if (far == cur) { cnt = -1; break; }     // 出现缺口，无法覆盖
12        cur = far; cnt++;                        // 选右端点最远的区间
13    }
14    cout << cnt;
15    return 0;
16}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Act { int s, e; };
04int main() {
05    Act a[4] = {{1,4},{2,5},{3,6},{4,7}};
06    sort(a, a + 4, [](Act x, Act y){ return x.s < y.s; });  // 按开始时间
07    int end[4] = {0}, rooms = 0;             // 各教室最早结束时间
08    for (int i = 0; i < 4; i++) {
09        int t = -1;
10        for (int j = 0; j < rooms; j++)      // 找最早结束且可复用的教室
11            if (end[j] <= a[i].s && (t == -1 || end[j] < end[t])) t = j;
12        if (t == -1) { t = rooms; rooms++; } // 没有可复用的，新开一间
13        end[t] = a[i].e;
14    }
15    cout << rooms;
16    return 0;
17}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Act { int id, s, e; };
04int main() {
05    Act a[4] = {{1,6,8},{2,1,4},{3,3,5},{4,0,6}};
06    sort(a, a + 4, [](Act x, Act y){ return x.e < y.e; });  // 按结束时间排序
07    for (int i = 0; i < 4; i++) cout << a[i].id << " ";
08    return 0;
09}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Seg { int l, r; };
04int main() {
05    Seg s[5] = {{1,3},{2,6},{8,10},{15,18},{16,17}};
06    sort(s, s + 5, [](Seg x, Seg y){ return x.l < y.l; });
07    int l = s[0].l, r = s[0].r, cnt = 1;
08    for (int i = 1; i < 5; i++) {
09        if (s[i].l <= r) r = max(r, s[i].r);   // 重叠，合并
10        else { cnt++; l = s[i].l; r = s[i].r; }  // 新的一段
11    }
12    cout << cnt;   // 合并后区间个数
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Item { int w, v; };             // 重量、价值
04int main() {
05    Item it[3] = {{10,60},{20,100},{30,120}};
06    double cap = 50, ans = 0;          // 背包容量 50，物品可分割
07    sort(it, it + 3, [](Item x, Item y){
08        return (double)x.v / x.w > (double)y.v / y.w; });  // 按单位价值排序
09    for (int i = 0; i < 3; i++) {
10        if (cap >= it[i].w) { ans += it[i].v; cap -= it[i].w; }
11        else { ans += (double)it[i].v * cap / it[i].w; break; }  // 取一部分
12    }
13    cout << (int)ans;
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int t[5] = {3, 1, 4, 1, 5};       // 每人接水时间
05    int n = 5;
06    sort(t, t + n);                    // 短的先接
07    long long sum = 0, wait = 0;
08    for (int i = 0; i < n; i++) {
09        wait += sum;                   // 轮到的人要等前面所有人
10        sum += t[i];
11    }
12    cout << wait;                      // 总等待时间
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int t[4] = {2, 5, 3, 1};
05    int n = 4;
06    sort(t, t + n);
07    long long sum = 0, total = 0;
08    for (int i = 0; i < n; i++) {
09        sum += t[i];
10        total += sum;                  // 每人"从开始到接完"的总时间
11    }
12    cout << total;
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int t[5] = {3, 1, 4, 1, 5};
05    int n = 5;
06    sort(t, t + n);                    // 1 1 3 4 5
07    int w1 = 0, w2 = 0;                // 两个窗口的累计时间
08    for (int i = 0; i < n; i++) {
09        if (w1 <= w2) w1 += t[i];      // 分配给更早空闲的窗口
10        else w2 += t[i];
11    }
12    cout << max(w1, w2);               // 全部接完的时间
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Item { int w, v; };
04int main() {
05    Item it[3] = {{10,60},{20,100},{30,120}};
06    int cap = 50, greedy = 0;          // 0/1 背包（不可分割），容量 50
07    sort(it, it + 3, [](Item x, Item y){
08        return (double)x.v / x.w > (double)y.v / y.w; });
09    for (int i = 0; i < 3; i++)
10        if (cap >= it[i].w) { greedy += it[i].v; cap -= it[i].w; }
11    cout << greedy;                    // 贪心结果（最优应为 220）
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string s = "1432219";              // 删 3 个数字使剩下最小
05    int k = 3;
06    for (int t = 0; t < k; t++) {
07        int pos = 0;
08        while (pos + 1 < s.size() && s[pos] <= s[pos + 1]) pos++;  // 找第一个峰
09        s.erase(pos, 1);               // 删掉峰顶
10    }
11    cout << s;
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {1, 2, 3, 4, 5};       // 五堆果子的重量
05    int n = 5, ans = 0;
06    sort(a, a + n);                    // 先排序：最小的两堆在最前面
07    for (int t = 1; t < n; t++) {      // 合并 n-1 次
08        int s = a[t - 1] + a[t];       // 取当前最小的两堆
09        ans += s;
10        a[t] = s;                      // 新堆放回
11        sort(a + t, a + n);            // 重新排序剩余部分
12    }
13    cout << ans;
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {2, 3, 5, 7};
05    int n = 4;
06    sort(a, a + n);
07    for (int t = 1; t < n; t++) {
08        int s = a[t - 1] + a[t];
09        cout << s << " ";              // 输出每次合并产生的新堆
10        a[t] = s;
11        sort(a + t, a + n);
12    }
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {1, 2, 3, 4, 5};       // 数轴上的 5 个点
05    int n = 5;
06    sort(a, a + n);
07    int mid = a[n / 2];                // 仓库建在中位数处
08    int total = 0;
09    for (int i = 0; i < n; i++) total += abs(a[i] - mid);
10    cout << total;                     // 到各点距离之和
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int w[4] = {2, 3, 5, 7};          // 叶子权值
05    int n = 4, wpl = 0;
06    sort(w, w + n);
07    for (int t = 1; t < n; t++) {     // 每次合并最小的两个
08        int s = w[t - 1] + w[t];
09        wpl += s;                     // 合并代价之和 = WPL
10        w[t] = s;
11        sort(w + t, w + n);
12    }
13    cout << wpl;
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Item { int w, v; };
04int main() {
05    Item it[3] = {{10,60},{20,100},{30,120}};
06    double cap = 50;                  // 背包容量 50，物品可分割
07    sort(it, it + 3, [](Item x, Item y){
08        return (double)x.v / x.w > (double)y.v / y.w; });   // 按单位价值排序
09    for (int i = 0; i < 3 && cap > 0; i++) {
10        int take = min((double)it[i].w, cap);   // 能装多少装多少
11        cout << take << " ";
12        cap -= take;
13    }
14    return 0;
15}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {1, 9, 2, 8, 3};       // 数轴上的 5 个点
05    int n = 5;
06    sort(a, a + n);
07    cout << a[n / 2];                  // 中位数位置
08    return 0;
09}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string s = "178543";               // 删 2 个数字使剩下最小
05    int k = 2;
06    for (int t = 0; t < k; t++) {
07        int pos = 0;
08        while (pos + 1 < s.size() && s[pos] <= s[pos + 1]) pos++;
09        s.erase(pos, 1);
10    }
11    cout << s;
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string a[3] = {"3", "32", "321"};
05    sort(a, a + 3, [](string x, string y){ return x + y < y + x; });  // 拼接比较器
06    for (int i = 0; i < 3; i++) cout << a[i];
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    string a[3] = {"3", "32", "321"};
05    sort(a, a + 3, [](string x, string y){ return x + y > y + x; });  // 反向比较器
06    for (int i = 0; i < 3; i++) cout << a[i];
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {2, 3, 1, 1, 4};       // 每个位置最多向前跳的步数
05    int n = 5, steps = 0, cur = 0, far = 0;
06    for (int i = 0; i < n - 1; i++) {
07        far = max(far, i + a[i]);     // 贪心：维护能到达的最远位置
08        if (i == cur) { steps++; cur = far; }  // 到达当前覆盖边界，步数加一
09    }
10    cout << steps;
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {3, 2, 1, 0, 4};
05    int n = 5, far = 0;
06    for (int i = 0; i < n; i++) {
07        if (i > far) break;            // 当前位置到不了
08        far = max(far, i + a[i]);
09    }
10    cout << (far >= n - 1 ? "YES" : "NO");
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {9, 8, 17, 6};          // 四堆纸牌
05    int n = 4, sum = 0;
06    for (int i = 0; i < n; i++) sum += a[i];
07    int avg = sum / n, cnt = 0, diff = 0;
08    for (int i = 0; i < n; i++) {
09        diff += a[i] - avg;            // 把差值"传递"给下一堆
10        if (diff != 0) cnt++;          // 差值为 0 说明不用移动
11    }
12    cout << cnt;
13    return 0;
14}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int t[4] = {1, 2, 5, 10};          // 4 人过桥时间（手电筒每次必须送回）
05    sort(t, t + 4);
06    int n = 4, ans = 0;
07    while (n > 3) {                    // 每次送走最慢的两人
08        int way1 = t[0] + 2 * t[1] + t[n - 1];     // 最快两人来回带
09        int way2 = 2 * t[0] + t[n - 2] + t[n - 1]; // 最快的人单独往返
10        ans += min(way1, way2);
11        n -= 2;
12    }
13    if (n == 3) ans += t[0] + t[1] + t[2];
14    else if (n == 2) ans += t[1];
15    else ans += t[0];
16    cout << ans;
17    return 0;
18}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[6] = {-2, 1, -3, 4, -1, 2};
05    int cur = 0, best = 0, L = 0, R = 0, tmp = 0;
06    for (int i = 0; i < 6; i++) {
07        cur += a[i];
08        if (cur < 0) { cur = 0; tmp = i + 1; }     // 和为负，重新开始
09        else if (cur > best) { best = cur; L = tmp; R = i; }   // 记录更优区间
10    }
11    cout << best << " " << L << " " << R;          // 最大和与区间左右端点
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Seg { int l, r; };              // 每个区间至少种一棵树
04int main() {
05    Seg s[4] = {{1,3},{2,5},{4,6},{5,8}};
06    sort(s, s + 4, [](Seg x, Seg y){ return x.r < y.r; });
07    int cnt = 0, pos = -1;
08    for (int i = 0; i < 4; i++)
09        if (s[i].l > pos) { cnt++; pos = s[i].r; }  // 区间选点
10    cout << cnt;
11    return 0;
12}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03struct Seg { int l, r; };
04int main() {
05    Seg s[4] = {{1,3},{2,5},{4,6},{5,8}};
06    sort(s, s + 4, [](Seg x, Seg y){ return x.r < y.r; });
07    int pos = -1;
08    for (int i = 0; i < 4; i++)
09        if (s[i].l > pos) { pos = s[i].r; cout << pos << " "; }   // 输出所选点
10    return 0;
11}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int t[5] = {3, 1, 4, 1, 5};       // 每人接水时间
05    pair<int,int> p[5];               // {用时, 编号}
06    for (int i = 0; i < 5; i++) p[i] = {t[i], i + 1};
07    sort(p, p + 5);                    // 默认先比用时、再比编号
08    for (int i = 0; i < 5; i++) cout << p[i].second << " ";   // 输出接水顺序
09    return 0;
10}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[7] = {3, -5, 2, -1, 4, -2, 3};
05    int cur = 0, best = 0;
06    for (int i = 0; i < 7; i++) {
07        cur += a[i];
08        if (cur < 0) cur = 0;
09        best = max(best, cur);
10    }
11    cout << best;
12    return 0;
13}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int coins[4] = {25, 10, 5, 1};
05    int money = 87, cnt = 0;
06    for (int i = 0; i < 4; i++) {
07        cnt += ______;            // 当前面额能用几张
08        money %= coins[i];
09    }
10    cout << cnt;
11    return 0;
12}

单选题：横线处应填入？

01#include <bits/stdc++.h>
02using namespace std;
03struct Act { int s, e; };
04int main() {
05    Act a[5] = {{1,4},{3,5},{0,6},{5,7},{3,8}};
06    sort(a, a + 5, [](Act x, Act y){ return x.e < y.e; });
07    int cnt = 0, last = -1;
08    for (int i = 0; i < 5; i++)
09        if (______) { cnt++; last = a[i].e; }   // 当前活动能选
10    cout << cnt;
11    return 0;
12}

单选题：横线处应填入？