1 solutions

  • 0
    @ 2025-7-6 22:46:16

    以下内容搬运自 小粉兔的爆笑赛时答疑

    Me, 10-23 15:53:47:
    “请你设计一个系统,对于到达的任务(包含任务到达时间,以及完成对应任务所需的时间),将其分发到两个队列。” 在本文指的是:任务到达时已经按照此时的状态(当前队列完成时间长短)进行了提交(任务总是在到达时向着较小的那个队列进行发射)。I still don't get it. What does this mean exactly?
    Me, 10-23 15:55:42:
    That is, does the schedule queue (the one that we need to implement) have any non-trivial (greedily put to the shorter queue) strategy?
    CCSP2024出题人, 10-23 15:57:16:
    No need for complex cases, trivial case only.
    -------------------------------------------------
    Me, 10-23 16:00:35:
    In "ioqueue", does the schedule system process the tasks chronically or it obeys the input order? I.e., do I need to sort the tasks by their arrival time?
    CCSP2024出题人, 10-23 16:01:52:
    You schedule them for the arrival time (the value array inputted)
    -------------------------------------------------
    Me, 10-23 16:13:31:
    Ahh, now I see... In "ioqueue", problemsetters originally thought a greedy algorithm is correct. But it turns out to be incorrect (althought it was a first-time-algorithm for some (most) of the contestants). The problemsetters realized the case and submitted a clarification. But until just then I still didn't get it. All in all, do you feel sorry for those contestants that came up with a "mistakenly correct" algorithm (e.g., myself)? By the way, how to type Chinese in the machine...?
    CCSP2024出题人, 10-23 16:23:03:
    Sorry for the inconvenence.
    

    这是一道按照原本题意来做,std 是错误的题目。当然这个题说的乱七八糟的,原本题意是什么已经不得而知了。

    反正 std 是任务按照到达时间排序,每个任务无脑地放在更短的那个队列里就行了。

    但是有一个很显然的错误在于,如果所有任务到达时间非常稀疏,那么第二个队列根本就是用不上的,此时第二个队列的用时最小值为 0,场上 7 个错误数据有 6 个是种情况。这得是多低能连这种问题都想不出来?

    具体的值域 DP 做法基本上就是 这题 的简化版。

    fi,vf_{i,v} 是第一个队列处理排序之后前 ii 个任务时延为 vv 的情况下,第二个队列的最小用时。初始状态有 f0,v=0f_{0,v}=0

    接下来显然有以下转移方程:fi,v=min(fi1,v10,max(fi1,v,ai)+10)f_{i,v}=\min (f_{i-1,v-10},\max(f_{i-1,v},a_i)+10),在合法的状态下作转移即可。

    在最终得到的答案中,在较大者最小的情况下取第二个最小的,输出先输出较小者即可。显然值域 V 的上限是 15000,复杂度是 O(nV)O(nV)

    Information

    ID
    97
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    2
    Tags
    # Submissions
    34
    Accepted
    1
    Uploaded By