优化HackerEarth午餐盒分配题解代码，解决Time Limit Exceeded问题

问题描述 #

Alice是餐厅经理，餐厅准备了N份午餐盒，计划分配给M所学校。第i所学校订购A[i]份午餐盒。她希望尽可能多地给学校分配午餐盒，规则是：给第i所学校的午餐盒要么是0份，要么是A[i]份。需要确定最多能分配到午餐盒的学校数量。

现有代码的问题 #

你的代码大部分测试用例通过，但超时的核心原因有两点：

1. 排序效率极低：使用冒泡排序，时间复杂度为O(m²)，当m数值较大（比如10万级别）时，排序环节会占用大量运行时间，直接触发超时。
2. 冗余逻辑：计数循环里的while (sum <= n)完全多余，内部仅执行一次count++就break，属于无意义的代码（虽对性能影响不大，但需清理）。

优化方案 #

• 替换高效排序算法：改用C标准库的qsort函数，底层实现为快速排序，平均时间复杂度O(m log m)，大数据量下性能远优于冒泡排序。
• 简化计数逻辑：删除冗余的while循环，直接在sum不超过n时递增计数。
• 优化数组存储：用动态分配内存替代变长数组，避免大m值导致的栈溢出问题（OJ环境下更稳妥）。

优化后的代码 #

#include <stdio.h>
#include <stdlib.h>

// qsort所需的升序比较函数
int compare(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        // 动态分配数组，避免栈溢出
        int *a = (int*)malloc(m * sizeof(int));
        
        for (int i = 0; i < m; i++) {
            scanf("%d", &a[i]);
        }
        
        // 快速排序，优先处理需求最少的学校
        qsort(a, m, sizeof(int), compare);
        
        int sum = 0, count = 0;
        for (int i = 0; i < m; i++) {
            if (sum + a[i] > n) {
                break;
            }
            sum += a[i];
            count++;
        }
        printf("%d\n", count);
        
        // 释放动态内存，避免泄漏
        free(a);
    }
    return 0;
}

额外说明 #

• qsort的比较函数严格遵循标准写法，返回两元素差值实现升序排序，确保我们优先分配需求最小的学校，从而得到最多的分配数量。
• 合并输入语句scanf("%d %d", &n, &m);减少IO操作次数，可略微提升运行效率。
• 动态分配的内存需用free释放，养成良好的编程习惯。

内容的提问来源于stack exchange，提问作者Devansh Kumar