luogu-B3959 [GESP202403 四级] 做题

GESP C++四级2024年3月真题。本题主要考察排序操作。难度不大⭐⭐★☆☆。本题在洛谷评定为普及-。

luogu-B3959 [GESP202403 四级] 做题

题目要求

题目描述

小杨同学为了提高自己的实力制定了做题计划，在第 $k$ 天时，他必须要完成 $k$ 道题，否则他就会偷懒。

小杨同学现在找到了一个题库，一共有 $n$ 套题单，每一套题单中有一定数量的题目。但是他十分挑剔，每套题单他只会使用一次，每一天也只能使用一套题单里的题目，之后那套题单就会弃之不用。对于每套题单，他不必完成题单内所有的题。

那么问题来了，小杨同学最多做题几天才偷懒呢？

输入格式

第一行，一个整数为 $n$，表示有多少套题单。
第二行 $n$ 个整数 $a_1, a_2, \dots a_n$，分别表示每套题单有多少道题。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

4
3 1 4 1

输出 #1

3

说明/提示

对全部的测试数据，保证 $1 \leq n \leq 10^6$，$1 \leq a_i \leq 10^9$。

题目分析

1. 问题分析

• 题目要求计算小杨同学最多能坚持做题几天
• 每天需要完成的题目数量等于天数（第k天需要做k道题）
• 每套题单只能使用一次，每天只能用一套题单
• 不需要完成题单内的所有题目

2. 核心算法

贪心策略：为了尽可能坚持更多天，应该合理分配题单

• 每天需要完成的题目数量递增（第1天1题，第2天2题，以此类推）
• 应该将题目数量较少的题单用于完成前面几天的任务
• 将题目数量较多的题单留给后面需要做更多题的天数这样可以最大化能坚持的天数，例如样例中的[3,1,4,1]，排序后为[1,1,3,4]：
  • 第1天需要1题，可以用第一个题单(1题)完成
  • 第2天需要2题，可以用第三个题单(3题)完成
  • 第3天需要3题，可以用第四个题单(4题)完成
  • 第4天需要4题，但剩下的题单只有1题，无法完成，所以最多坚持3天

因此，代码核心步骤为：

• 将题单按题目数量从小到大排序
• 遍历每套题单，判断是否能满足当天的做题需求
  • 如果当前题单题目数量大于等于需要做的题目数(days+1)，则可以继续坚持
  • 否则则继续检查下一个题单

3. 时间复杂度分析

   • 排序需要 $O(n\log n)$ 的时间复杂度
   • 遍历题单需要 $O(n)$ 的时间复杂度
   • 总体时间复杂度为 $O(n\log n)$

4. 空间复杂度分析

   • 需要一个数组存储题单信息
   • 空间复杂度为 $O(n)$

{% include custom/custom-post-content-inner.html %}

示例代码

#include <algorithm>
#include <iostream>

// 存储每套题单的题目数量，最大长度为1000005
int ary[1000005];
int main() {
    // 输入题单数量n
    int n;
    std::cin >> n;
    
    // 输入每套题单的题目数量
    for (int i = 0; i < n; i++) {
        std::cin >> ary[i];
    }

    // 将题单按题目数量从小到大排序
    std::sort(ary, ary + n);

    // days记录可以坚持的天数
    int days = 0;

    // 遍历每套题单
    for (int i = 0; i < n; i++) {
        // 如果当前题单的题目数量大于等于需要做的题目数(days+1)
        // 则可以用这套题单完成当天的任务
        if (ary[i] >= days + 1) {
            days++;
        }
    }

    // 输出最终可以坚持的天数
    std::cout << days;
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号