题解 | #改考卷#

解题思路

这是一个贪心算法问题。具体要求：

$n$ 个组的试卷需要批改，第 $i$ 组有 $s_i$ 个学生
每次从桌上取出一组试卷进行批改
批改完后，将学生自己的试卷放在桌面试卷最下方
需要判断是否存在一种访问顺序，使得每组学生都能拿到自己的试卷

解决方案：

找出人数最多的组 $max$
计算其他所有组的总人数 $sum$
如果 $max > sum$ ，则不可能完成分配（因为最大组的试卷会占用太多位置）
否则一定存在合理的分配方案

代码

c++
java
python

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 读入每组人数并找出最大值
    int max_students = 0;
    int total_sum = 0;
    for(int i = 0; i < n; i++) {
        int students;
        cin >> students;
        total_sum += students;
        max_students = max(max_students, students);
    }
    
    // 判断是否可能完成分配
    total_sum -= max_students;  // 除去最大组的人数
    if(max_students > total_sum) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读入组数
        int n = sc.nextInt();
        
        // 读入每组人数并找出最大值
        int maxStudents = 0;
        int totalSum = 0;
        for(int i = 0; i < n; i++) {
            int students = sc.nextInt();
            totalSum += students;
            maxStudents = Math.max(maxStudents, students);
        }
        
        // 判断是否可能完成分配
        totalSum -= maxStudents;  // 除去最大组的人数
        if(maxStudents > totalSum) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}

def solve():
    # 读入组数
    n = int(input())
    
    # 读入每组人数
    students = list(map(int, input().split()))
    
    # 找出最大值和总和
    max_students = max(students)
    total_sum = sum(students)
    
    # 判断是否可能完成分配
    total_sum -= max_students  # 除去最大组的人数
    if max_students > total_sum:
        print("No")
    else:
        print("Yes")

if __name__ == "__main__":
    solve()

算法及复杂度

算法：贪心算法
时间复杂度： $\mathcal{O}(n)$ - 只需要遍历一次数组
空间复杂度： $\mathcal{O}(1)$ - 只需要常数空间存储最大值和总和