1 solutions
-
0
以下内容搬运自 小粉兔的爆笑赛时答疑:
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 做法基本上就是 这题 的简化版。
设 是第一个队列处理排序之后前 个任务时延为 的情况下,第二个队列的最小用时。初始状态有 。
接下来显然有以下转移方程:,在合法的状态下作转移即可。
在最终得到的答案中,在较大者最小的情况下取第二个最小的,输出先输出较小者即可。显然值域 V 的上限是 15000,复杂度是 。
Information
- ID
- 97
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 2
- Tags
- # Submissions
- 34
- Accepted
- 1
- Uploaded By