【牛客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)。核心在于利用有序数据优先处理高收益组合，降低补充成本。此思路可扩展至类似资源分配场景，具备实用性与算法优化价值。