1 solutions

  • -1
    @ 2024-3-9 22:06:30

    对于 20%的数据,n<=15;

    枚举要做哪些作业,判断是否可行。 可行只需要满足:对于任意的 i,小于 i 的Di的数量不能超过 i 个。 O(n*2^n) 对于 60%的数据,n<=1000; 考虑一个贪心:对于最后一个单位时间,把这时能做的分数最大的作业做掉。依此倒着向前贪心,每次选最大的。 证明:若最优方案该作业不在这一时刻做,那么可以把这个作业和原方案中这一时刻做的作业换过来,也是一个合法方案。 朴素的实现方法可以得到60分。

    若使用vector和priority_queue,时间复杂度为O(nlogn),得分100分。

    • 1

    Information

    ID
    324
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    # Submissions
    16
    Accepted
    4
    Uploaded By