题目分析本题要求小杨在避免连续学习两道相同知识点题目的前提下用最少的题目数量让 m 种算法的掌握程度都至少达到 k。每道题最多学习一次学习第 i 道题可以让第 ai 种算法的掌握程度提高 bi。核心难点在于「连续学习两道相同知识点的题目是不好的」这一约束。这意味着在选出的题目序列中不能出现相邻两项知识点相同的情况。解题思路本题可以采用二分答案 贪心验证的思路二分答案对需要学习的题目数量 x 进行二分判断能否选出 x 道题满足目标。贪心验证对于给定的 x按知识点分组考虑优先选择提升量大的题目并检查是否存在一种排列方式使得相邻题目知识点不同。关键结论设选出题目中数量最多的知识点组有 cnt 道题总题数为 x。若 cnt 超过 (x 1) / 2则无论怎样排列都会出现相邻两道题知识点相同的情况此时无解。因此验证时需保证cnt (x 1) / 2算法步骤对每种算法将其所有题目的提升量 b 从大到小排序。二分答案 x判断是否存在一种选择方案从每种算法中选若干道题总数为 x且每种算法选出的题目提升量之和至少为 k同时满足「最多知识点组数量不超过 (x1)/2」。贪心选取时优先选提升量大的题目若某算法已选题目数过多导致无法满足排列约束则调整选择。参考代码C#include bits/stdc.h using namespace std; int main() { int m, n, k; cin m n k; vectorint a(n), b(n); for (int i 0; i n; i) cin a[i]; for (int i 0; i n; i) cin b[i]; vectorvectorint groups(m 1); for (int i 0; i n; i) { groups[a[i]].push_back(b[i]); } for (int i 1; i m; i) { sort(groups[i].rbegin(), groups[i].rend()); } // 二分答案 int lo 0, hi n, ans -1; while (lo hi) { int mid (lo hi) / 2; // 判断能否选 mid 道题 vectorlong long sum(m 1, 0); vectorint cnt(m 1, 0); int total 0; for (int i 1; i m; i) { int take min((int)groups[i].size(), mid); for (int j 0; j take; j) { sum[i] groups[i][j]; cnt[i]; total; } } if (total mid) { // 题目不够需要从各组中补选 // 这里简化处理若总题数不足 mid则不可行 lo mid 1; continue; } // 检查是否每种算法都达到 k bool ok true; for (int i 1; i m; i) { if (sum[i] k) { ok false; break; } } if (!ok) { lo mid 1; continue; } // 检查排列约束最多组数量不超过 (mid1)/2 int maxCnt 0; for (int i 1; i m; i) maxCnt max(maxCnt, cnt[i]); if (maxCnt (mid 1) / 2) { lo mid 1; continue; } ans mid; hi mid - 1; } cout ans endl; return 0; }复杂度分析时间复杂度O(n log n n log n)排序 O(n log n)二分验证 O(n log n)。空间复杂度O(n m)。总结本题的关键在于将「避免连续相同知识点」转化为排列约束条件即最多知识点组的数量不能超过总题数的一半向上取整。结合二分答案和贪心选取可以在 O(n log n) 时间内求解。
题目分析本题要求小杨在避免连续学习两道相同知识点题目的前提下用最少的题目数量让 m 种算法的掌握程度都至少达到 k。每道题最多学习一次学习第 i 道题可以让第 ai 种算法的掌握程度提高 bi。核心难点在于「连续学习两道相同知识点的题目是不好的」这一约束。这意味着在选出的题目序列中不能出现相邻两项知识点相同的情况。解题思路本题可以采用二分答案 贪心验证的思路二分答案对需要学习的题目数量 x 进行二分判断能否选出 x 道题满足目标。贪心验证对于给定的 x按知识点分组考虑优先选择提升量大的题目并检查是否存在一种排列方式使得相邻题目知识点不同。关键结论设选出题目中数量最多的知识点组有 cnt 道题总题数为 x。若 cnt 超过 (x 1) / 2则无论怎样排列都会出现相邻两道题知识点相同的情况此时无解。因此验证时需保证cnt (x 1) / 2算法步骤对每种算法将其所有题目的提升量 b 从大到小排序。二分答案 x判断是否存在一种选择方案从每种算法中选若干道题总数为 x且每种算法选出的题目提升量之和至少为 k同时满足「最多知识点组数量不超过 (x1)/2」。贪心选取时优先选提升量大的题目若某算法已选题目数过多导致无法满足排列约束则调整选择。参考代码C#include bits/stdc.h using namespace std; int main() { int m, n, k; cin m n k; vectorint a(n), b(n); for (int i 0; i n; i) cin a[i]; for (int i 0; i n; i) cin b[i]; vectorvectorint groups(m 1); for (int i 0; i n; i) { groups[a[i]].push_back(b[i]); } for (int i 1; i m; i) { sort(groups[i].rbegin(), groups[i].rend()); } // 二分答案 int lo 0, hi n, ans -1; while (lo hi) { int mid (lo hi) / 2; // 判断能否选 mid 道题 vectorlong long sum(m 1, 0); vectorint cnt(m 1, 0); int total 0; for (int i 1; i m; i) { int take min((int)groups[i].size(), mid); for (int j 0; j take; j) { sum[i] groups[i][j]; cnt[i]; total; } } if (total mid) { // 题目不够需要从各组中补选 // 这里简化处理若总题数不足 mid则不可行 lo mid 1; continue; } // 检查是否每种算法都达到 k bool ok true; for (int i 1; i m; i) { if (sum[i] k) { ok false; break; } } if (!ok) { lo mid 1; continue; } // 检查排列约束最多组数量不超过 (mid1)/2 int maxCnt 0; for (int i 1; i m; i) maxCnt max(maxCnt, cnt[i]); if (maxCnt (mid 1) / 2) { lo mid 1; continue; } ans mid; hi mid - 1; } cout ans endl; return 0; }复杂度分析时间复杂度O(n log n n log n)排序 O(n log n)二分验证 O(n log n)。空间复杂度O(n m)。总结本题的关键在于将「避免连续相同知识点」转化为排列约束条件即最多知识点组的数量不能超过总题数的一半向上取整。结合二分答案和贪心选取可以在 O(n log n) 时间内求解。
