【牛客13256题解析】贪心算法优化题目组合问题:三元组与二元组的解题思路

一、题目解读
牛客13256题要求处理一组题目难度数据,通过组合三元组(难度差≤20)或二元组(难度差≤10)来重新编排题目,计算需要补充的最小题目数量。题目本质是资源分配与优化问题,需高效组合现有题目以满足条件,减少额外补充量。
二、解题思路
参考代码采用贪心策略:首先对题目难度排序,随后从低到高遍历,优先匹配三元组(最大效率组合),若无法匹配则尝试二元组,最后处理单独题目。通过分情况讨论,逐步消耗已有题目并统计补充需求,确保全局最优解。
三、解题步骤
1. 输入与预处理:读取n道题目难度并排序,确保后续组合判断的高效性。
2. 遍历与判断:
若当前位置可组成三元组(diff[i+2]-diff[i]≤20),直接消耗3题;
若可组成二元组(diff[i+1]-diff[i]≤10),消耗2题并补充1题;
单独题目则补充2题,消耗1题。
3. 统计结果:累加补充次数,最终输出总需补充量。
四、代码与注释
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false); // 加快输入输出
cin.tie(nullptr);
int n;
cin >> n; // 输入题目数量
vector<int> difficulties(n);
for(int i = 0; i < n; ++i) {
cin >> difficulties[i]; // 读取难度数据
}
sort(difficulties.begin(), difficulties.end()); // 排序,为后续贪心策略准备
int res = 0; // 记录需补充的题目数
for(int i = 0; i < n; ) { // 遍历时通过i增量控制消耗
// 检查三元组条件
if(i + 2 < n && difficulties[i+2] - difficulties[i] <= 20) {
i += 3; // 消耗3题,无需补充
}
// 检查二元组条件
else if(i + 1 < n && difficulties[i+1] - difficulties[i] <= 10) {
res += 1; // 需补充1题
i += 2; // 消耗2题
}
// 单独题目处理
else {
res += 2; // 需补充2题
i += 1; // 消耗1题
}
}
cout << res << endl;
return 0;
}五、总结
该解法通过排序+贪心策略,将题目组合问题转化为逐层匹配的过程,时间复杂度O(nlogn)(排序)+O(n)(遍历),空间复杂度O(n)。核心在于利用有序数据优先处理高收益组合,降低补充成本。此思路可扩展至类似资源分配场景,具备实用性与算法优化价值。
原创内容 转载请注明出处






