牛客网13256头条校招解析：贪心算法解决题目分组难题

一、问题分析

本题需要将n道题目分组，每组3道题目满足特定难度条件，求最少需要补充的题目数量。关键在于如何高效地分组现有题目，最小化补充题目。

二、C++解决方案

#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; ) {
        // 检查是否能组成有效三元组
        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;
}

三、算法详解

1. 排序预处理：

• 首先对题目难度排序，便于分组处理

• 时间复杂度O(nlogn)

2. 贪心策略：

• 优先尝试组成完整三元组

• 次优组成二元组+补充1题

• 最后处理单独题目+补充2题

3. 边界处理：

• 处理数组末尾不足3题的情况

• 确保所有题目都被处理

四、常见错误

1. 未排序直接处理

2. 边界条件处理不当

3. 贪心策略顺序错误

4. 输入输出效率问题

扩展思考

1. 如果分组条件变化如何调整算法？

2. 如何处理更大规模的数据？

3. 如何扩展为动态难度调整？