解题思路

  1. 基本思路：

    • 先对题目难度进行排序。
    • 从最小难度开始，尝试组合每场考试的三道题。
    • 每找到一组题目后，标记这些题目为已使用。
    • 统计需要补充的题目数量。

  2. 实现方法：

    • 使用贪心策略，优先使用难度相近的题目组合。
    • 使用 数组标记已使用的题目。
    • 对于每组题目，确保相邻题目难度差不超过 。
    • 计算每组不足三道题时需要补充的题目数量。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minExtraQuestions(int n, vector<int>& difficulties) {
    sort(difficulties.begin(), difficulties.end());
    vector<bool> used(n, false);
    int extra = 0;
    
    // 从最小的数开始尝试组合
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        
        // 找第一道题
        int first = difficulties[i];
        used[i] = true;
        
        // 找第二道题
        int second = -1, second_idx = -1;
        for (int j = i + 1; j < n; j++) {
            if (!used[j] && difficulties[j] - first <= 10) {
                second = difficulties[j];
                second_idx = j;
                break;
            }
        }
        
        // 找第三道题
        int third = -1, third_idx = -1;
        if (second != -1) {
            for (int j = second_idx + 1; j < n; j++) {
                if (!used[j] && difficulties[j] - second <= 10) {
                    third = difficulties[j];
                    third_idx = j;
                    break;
                }
            }
        }
        
        // 计算需要补充的题目数
        if (second == -1) {  // 只有第一道题
            extra += 2;
        } else if (third == -1) {  // 只有两道题
            used[second_idx] = true;
            extra += 1;
        } else {  // 找到三道题
            used[second_idx] = true;
            used[third_idx] = true;
        }
    }
    
    return extra;
}

int main() {
    int n;
    cin >> n;
    vector<int> difficulties(n);
    for (int i = 0; i < n; i++) {
        cin >> difficulties[i];
    }
    cout << minExtraQuestions(n, difficulties) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int minExtraQuestions(int n, int[] difficulties) {
        Arrays.sort(difficulties);
        boolean[] used = new boolean[n];
        int extra = 0;
        
        // 从最小的数开始尝试组合
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            
            // 找第一道题
            int first = difficulties[i];
            used[i] = true;
            
            // 找第二道题
            int second = -1, second_idx = -1;
            for (int j = i + 1; j < n; j++) {
                if (!used[j] && difficulties[j] - first <= 10) {
                    second = difficulties[j];
                    second_idx = j;
                    break;
                }
            }
            
            // 找第三道题
            int third = -1, third_idx = -1;
            if (second != -1) {
                for (int j = second_idx + 1; j < n; j++) {
                    if (!used[j] && difficulties[j] - second <= 10) {
                        third = difficulties[j];
                        third_idx = j;
                        break;
                    }
                }
            }
            
            // 计算需要补充的题目数
            if (second == -1) {  // 只有第一道题
                extra += 2;
            } else if (third == -1) {  // 只有两道题
                used[second_idx] = true;
                extra += 1;
            } else {  // 找到三道题
                used[second_idx] = true;
                used[third_idx] = true;
            }
        }
        
        return extra;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] difficulties = new int[n];
        for (int i = 0; i < n; i++) {
            difficulties[i] = sc.nextInt();
        }
        System.out.println(minExtraQuestions(n, difficulties));
    }
}

def min_extra_questions(n, difficulties):
    difficulties.sort()
    used = [False] * n
    extra = 0
    
    # 从最小的数开始尝试组合
    for i in range(n):
        if used[i]:
            continue
            
        # 找第一道题
        first = difficulties[i]
        used[i] = True
        
        # 找第二道题
        second = -1
        second_idx = -1
        for j in range(i + 1, n):
            if not used[j] and difficulties[j] - first <= 10:
                second = difficulties[j]
                second_idx = j
                break
                
        # 找第三道题
        third = -1
        third_idx = -1
        if second != -1:
            for j in range(second_idx + 1, n):
                if not used[j] and difficulties[j] - second <= 10:
                    third = difficulties[j]
                    third_idx = j
                    break
        
        # 根据找到的题目数量计算需要补充的题目
        if second == -1:  # 只有第一道题
            extra += 2
        elif third == -1:  # 只有两道题
            used[second_idx] = True
            extra += 1
        else:  # 找到三道题
            used[second_idx] = True
            used[third_idx] = True
    
    return extra

if __name__ == "__main__":
    n = int(input())
    difficulties = list(map(int, input().split()))
    print(min_extra_questions(n, difficulties))

算法及复杂度

  • 算法：贪心算法
  • 时间复杂度：，其中 为题目数量
  • 空间复杂度：，用于存储已使用题目的标记