用最少题目让 m 种算法都达到 k,且不能连续做同知识点的题。
有 m 种算法,初始掌握度都是 0。有 n 道题,第 i 道题属于知识点 aᵢ,学习后能让该算法的掌握度提高 bᵢ。每道题最多学一次。
目标是让每种算法的掌握度都至少为 k,同时不能连续学习两道相同知识点的题目。求最少需要学习多少道题;无解输出 -1。
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 | 不能连续两道题属于同一知识点 |
M ≤ T − M + 1;若不满足,就多选一些别知识点的题把 T 撑大知识点 a = [1, 1, 2, 3, 3],提升量 b = [9, 1, 10, 10, 1]。
算法 1:题目 b = {9, 1} → 降序 [9, 1],总和 10
算法 2:题目 b = {10} → [10],总和 10
算法 3:题目 b = {10, 1} → 降序 [10, 1],总和 11
三组都 ≥ k = 10 ✓
算法 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)
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
各组题目总数 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 ✓ 无连续相同
m = 2,n = 4,k = 10,a = [1, 1, 1, 2],b = [1, 2, 7, 10]。
算法 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)
T0 = 3 + 1 = 4,M = 3
要求 T ≥ 2M − 1 = 5
所以 T = max(4, 5) = 5
但两组总共只有 4 道题(sz = (3, 1))
需要 5 道但只有 4 道
Σ 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,即 T ≥ 2M − 1 ✓。这个"插空"思路和"座位安排""重排字符串"是同一个模型。每组各自取最少的题达标,再用交错条件判定并"补题"
base_j(每组最少题数)、M = max base_j、sz_j(每组题目总数)。答案或 -1 完全由这三个量决定,不需要真的去排列题目。枚举题目的学习顺序并检查条件
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 分组 + 判定 | O(n log n) | ✅ 稳过 |
| 枚举顺序 | O(n!) | ❌ 不可行 |
第一行输入 m n k,第二行输入知识点,第三行输入提升量。
点按钮开始 →
#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),它就变成"绝对多数",必然出现连续两道同类题。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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 | 最终判定 | 凑不出这么多题就无解 |
M ≤ T − M(应为 M ≤ T − M + 1,差一个 1 就会错);④ 忽略 min(sz_j, M) 的上限。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 5 10 | 4 | 题面样例 1 |
2 4 10 | -1 | 题面样例 2(插不满) |
1 1 5 | 1 | 一种算法一道题,恰好达标 |
1 2 5 | -1 | 只有一种算法,需要 2 道题就会连续同类 |
2 2 5 | 2 | 两种算法各一道,可交错 |
2 3 3 | 3 | base=(2,1),M=2,T=3;交错可行 → 3 道 |
M ≤ T − M + 1。需要存下每组的题目提升量。
✅ 约 200 万次操作,瞬间完成。本题难点在"想到交错条件",而不在复杂度。
// 本题的三个核心量 // 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,条件里的系数就相应变化——这也是"任务调度器"类问题的常见变体。)