GESP 题解库 / 6 级题解 / [GESP202409 六级] 算法学习 · 第 13 / 27 题
GESP202409 六级 · P11247 · 中等

算法学习

用最少题目让 m 种算法都达到 k,且不能连续做同知识点的题。

📊
m, n ≤ 10⁵
数据规模
🔢
long long
掌握度范围
⚡
O(n log n)
时间复杂度
🎯
分组贪心 + 交错可行性
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有 m 种算法,初始掌握度都是 0。有 n 道题,第 i 道题属于知识点 aᵢ,学习后能让该算法的掌握度提高 bᵢ。每道题最多学一次。

目标是让每种算法的掌握度都至少为 k,同时不能连续学习两道相同知识点的题目。求最少需要学习多少道题;无解输出 -1。

💡
人话翻译:分两步——
① 每种算法各自"用最少的题达标":把该知识点的题目按 b 从大到小排,取前缀直到和 ≥ k,这个数量记为 base_j。
② 解决"不能连续同知识点":经典结论——若某种算法选了 cnt 道题,总量为 T,则能交错排开 ⟺ 最大 cnt ≤ T − 最大 cnt + 1。

🔍 关键词提取

分组贪心交错排列可行性排序取前缀总数与最大值

已知条件

项目说明
输入第一行 m、n、k;第二行 a₁…aₙ;第三行 b₁…bₙ
输出最少题目数,无解输出 −1
数据范围1 ≤ m, n, bᵢ, k ≤ 10⁵
约束 1每种算法掌握度都要 ≥ k
约束 2不能连续两道题属于同一知识点

需要解决的问题

02
思维导图
整理解题思路的全貌
📚 分组求 base + 交错可行性
📊 第一步
同知识点题按 b 降序
取前缀直到和 ≥ k
得到 base_j(最少题数)
若总和 < k → -1
📐 第二步
设 M = max base_j
T0 = Σ base_j
交错条件:M ≤ T − M + 1
即 T ≥ 2M − 1
🔧 第三步
T = max(T0, 2M − 1)
需要"多选题"把 T 撑到这么大
每种算法最多贡献 min(sz_j, M) 道
若 Σ min(sz_j, M) < T → -1
⚠️ 易错点
忘记先判 -1
同知识点没按 b 降序取前缀
交错条件写反
忽略"每题只能学一次"的容量上限
03
样例手算推导
两个样例的完整推演

🧮 样例 1:m = 3,n = 5,k = 10

知识点 a = [1, 1, 2, 3, 3],提升量 b = [9, 1, 10, 10, 1]。

1
按知识点分组,并各自降序

算法 1:题目 b = {9, 1} → 降序 [9, 1],总和 10

算法 2:题目 b = {10} → [10],总和 10

算法 3:题目 b = {10, 1} → 降序 [10, 1],总和 11

三组都 ≥ k = 10 ✓

2
求各组的 base

算法 1:[9] 才 9 < 10,[9, 1] = 10 ≥ 10 → base₁ = 2

算法 2:[10] = 10 ≥ 10 → base₂ = 1

算法 3:[10] = 10 ≥ 10 → base₃ = 1

base = (2, 1, 1)

3
检查交错条件

T0 = 2 + 1 + 1 = 4

M = max(2, 1, 1) = 2

要求 M ≤ T0 − M + 1,即 2 ≤ 4 − 2 + 1 = 3 ✓ 成立

所以 T = max(4, 2×2−1) = max(4, 3) = 4

T = 4

4
验证容量

各组题目总数 sz = (2, 1, 2)

Σ min(sz_j, M) = min(2,2) + min(1,2) + min(2,2)

= 2 + 1 + 2 = 5 ≥ T = 4 ✓

所以可行

✅ 答案 4

一种方案:题目 1、3、4、2 → 知识点 1、2、3、1 ✓ 无连续相同

🔑
注意算法 1 必须做两道题:它最大的题只给 9 分(< 10),所以必须再做一道 b=1 的。这就是为什么"按 b 降序取前缀"很重要——如果先做 b=1 的,会误以为要 3 道题。

🧮 样例 2:为什么是 -1

m = 2,n = 4,k = 10,a = [1, 1, 1, 2],b = [1, 2, 7, 10]。

1
分组与 base

算法 1:b = {1, 2, 7} → 降序 [7, 2, 1],总和 10 ≥ 10 ✓

7 + 2 = 9 < 10;7 + 2 + 1 = 10 → base₁ = 3

算法 2:b = {10} → base₂ = 1

base = (3, 1)

2
检查交错条件

T0 = 3 + 1 = 4,M = 3

要求 T ≥ 2M − 1 = 5

所以 T = max(4, 5) = 5

但两组总共只有 4 道题(sz = (3, 1))

需要 5 道但只有 4 道

3
结论

Σ min(sz_j, M) = min(3,3) + min(1,3) = 3 + 1 = 4

4 < T = 5 → 无法凑够

所以输出 -1

❌ 输出 -1

📊 直观理解

算法 1 必须做 3 道题(因为它的题给分太碎),而算法 2 只有 1 道题。要想让 3 道"1 类题"不挨在一起,中间必须插入至少 2 道其他题,但其他知识点总共只有 1 道——插不满,所以无解。

⚠️
交错条件的直觉:把最多的那类题想象成"隔板",要让它们两两不相邻,就需要在它们之间插入至少 M − 1 道别的题;而别的题共有 (T − M) 道。所以条件就是 M − 1 ≤ T − M,即 T ≥ 2M − 1 ✓。这个"插空"思路和"座位安排""重排字符串"是同一个模型。
04
解法对比
分组贪心 + 判定 vs 状压/搜索

⚔️ 解法对比

🟢 分组 + 判定(推荐) 推荐

每组各自取最少的题达标,再用交错条件判定并"补题"

  • 时间 O(n log n)
  • n = 10⁵ 时约 10⁶
  • 代码 40 行
  • 空间 O(n + m)
💡
三个关键量:base_j(每组最少题数)、M = max base_j、sz_j(每组题目总数)。答案或 -1 完全由这三个量决定,不需要真的去排列题目。

🟠 搜索学习顺序

枚举题目的学习顺序并检查条件

  • n! 种顺序
  • n = 10⁵ 完全不可行
  • 只能处理 n ≤ 9 的测试点
  • 不适合
⚠️
为什么不需要搜索:因为"能否交错"只取决于每类的数量,与具体顺序无关(这是经典的排列存在性结论)。识别出"只需判断数量关系"是本题的关键一步。

📈 性能对比

方案复杂度可行性
分组 + 判定O(n log n)✅ 稳过
枚举顺序O(n!)❌ 不可行
05
算法流程图
分组求 base,再判定交错可行性
开始读入 m、n、k、数组 a、数组 b按知识点分组,把每组的 b 降序排序遍历每个知识点 j该组 b 的总和是否小于 k?是 ✓输出 -1 并结束否 ✗继续取前缀直到和 ≥ k,得到 base_j;T0 加上 base_jM = max base_j;T = max(T0, 2M − 1)Σ min(sz_j, M) 是否不小于 T?是 ✓输出 T否 ✗输出 -1结束处理下一个知识点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📚 最少学习题目数

第一行输入 m n k,第二行输入知识点,第三行输入提升量。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

int main() {
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);

    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    vector<vector<long long>> g(m + 1);       // 按知识点分组
    for (int i = 0; i < n; i++) {
        long long b;
        scanf("%lld", &b);
        g[a[i]].push_back(b);
    }

    long long T0 = 0;
    int M = 0;
    vector<int> base(m + 1), sz(m + 1);

    for (int j = 1; j <= m; j++) {
        sort(g[j].begin(), g[j].end(), greater<long long>());   // 降序
        sz[j] = (int)g[j].size();

        long long s = 0;
        int cnt = 0;
        for (int t = 0; t < (int)g[j].size(); t++) {
            if (s >= k) break;
            s += g[j][t];
            cnt++;
        }
        if (s < k) { puts("-1"); return 0; }      // 该算法永远达不到 k

        base[j] = cnt;
        T0 += cnt;
        M = max(M, cnt);
    }

    long long T = max(T0, 2LL * M - 1);           // 交错条件要求的下界

    // 每种算法最多贡献 min(sz[j], M) 道(受交错条件限制)
    long long capSum = 0;
    for (int j = 1; j <= m; j++) capSum += min((long long)sz[j], (long long)M);

    if (capSum < T) puts("-1");
    else printf("%lld\n", T);
    return 0;
}
🔑
为什么"最多贡献 min(sz_j, M)"?一方面不能超过该知识点的题目总数 sz_j;另一方面,若某一类超过 M = floor((T+1)/2),它就变成"绝对多数",必然出现连续两道同类题。
所以每类的上限是两者取小。把"总数 T"和"每类上限"对齐后,问题就变成"能否凑出恰好 T 道题"——只要总和上限够,就一定能凑(因为从 base 往上加是连续的)。

📖 关键几行怎么看

代码作用为什么这样写
sort(g[j], greater)组内降序优先用大 b 的题,题数最少
if (s < k) return -1无解判定该算法所有题加起来都不够
T = max(T0, 2M - 1)交错下界多数类必须能被其他类"插开"
capSum += min(sz[j], M)容量上限每类题数既受总数限制也受 M 限制
if (capSum < T) -1最终判定凑不出这么多题就无解
⚠️
四个坑:① 忘记先判"某算法总和 < k"的无解情况;② 组内忘记降序(会导致 base 偏大);③ 交错条件写成 M ≤ T − M(应为 M ≤ T − M + 1,差一个 1 就会错);④ 忽略 min(sz_j, M) 的上限。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 5 10
1 1 2 3 3
9 1 10 10 1
4题面样例 1
2 4 10
1 1 1 2
1 2 7 10
-1题面样例 2(插不满)
1 1 5
1
5
1一种算法一道题,恰好达标
1 2 5
1 1
3 3
-1只有一种算法,需要 2 道题就会连续同类
2 2 5
1 2
5 5
2两种算法各一道,可交错
2 3 3
1 1 2
2 2 5
3base=(2,1),M=2,T=3;交错可行 → 3 道
✅
自查清单:① 组内降序了吗?② 交错条件对吗?③ 检查了每题只能用一次吗?

🚨 易错点清单

⚠️
组内不排序:必须按 b 降序取前缀,否则 base 偏大。
⚠️
交错条件差一个 1:应为 M ≤ T − M + 1。
⚠️
忘记判无解:某算法总和 < k 时直接输出 −1。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(n + m)
n 最大
10⁵
运算量
约 2 × 10⁶

时间怎么算的?

空间都用在哪?

需要存下每组的题目提升量。

✅ 约 200 万次操作,瞬间完成。本题难点在"想到交错条件",而不在复杂度。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 本题的三个核心量
// base_j : 第 j 种算法"用最少题达标"需要的题数
// M      : max base_j(多数类的规模)
// T      : 实际需要学习的总题数 = max(Σbase_j, 2M - 1)

// "不能连续同类"的通用判定(重排字符串模型)
// 设有若干类元素,数量为 cnt_1..cnt_m,总数 T
// 能排成"相邻不同"的排列  <=>  max cnt_i <= T - max cnt_i + 1
// 等价于 T >= 2 * max cnt_i - 1

// 这个结论的直觉(插空法)
// 把最多的那一类当作隔板,需要插入至少 (M - 1) 个其他元素
// 其他元素有 (T - M) 个,所以要求 M - 1 <= T - M

// 类似题目
// - 重排字符串使相邻字符不同(LeetCode 767)
// - 任务调度器 / 相同任务间隔冷却
// - 分组后交错排列的所有问题

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
插空法多数类作隔板所有"相邻不能相同"的排列问题
分组贪心组内降序取前缀"用最少资源达标"类问题
上界判定min(sz_j, M) 之和能否凑够所需的题数
🌟
思考题:如果题目改成"不能连续学习三道同知识点的题"(允许连续两道相同),交错条件会怎么变?(提示:那就变成"多数类最多只能占 2 × (其他 + 1)",即 M ≤ 2(T − M + 1)。把"允许的连续长度"从 1 改成 2,条件里的系数就相应变化——这也是"任务调度器"类问题的常见变体。)