G4008 [GESP202403 四级] 做题 题解

知识点：排序、贪心、模拟。

解题思路

将题目难度升序排列，当前已连续完成d-1天时，仅选难度至少d的题支持第d天，选到后d加1。

为什么正确

当前用最小可行难度的题不会比用更难题损害后续选择，贪心得到最长连续天数。

易错点

小于当前天数的题跳过，不能让它消耗一天；答案是d-1。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    sort(a.begin(),a.end());
    int d=1;
    for(int x:a)if(x>=d)d++;
    cout<<d-1;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。