Weekly Contest 318
第四题想不出来就去看世界赛了 第一次当Q3 gang
1.简单说就是操作后把不为0的元素加到新阵列里最后再补满0
看到有人用 sort(key = lambda x : not x) 去把0移到最后
好耶 我下次也要用
2.用 2-pointer iterate右界 维护一个set去记目前区间有哪些元素
如果右界元素存在于目前的set就不停拿出左界元素 直到拿出和右界一样的元素
如果右界-左界==k 就能更新答案 小于的话 就继续推进右界
大于的话也是拿出左界元素
总之就是需要保证左界右界没有重复元素
3.就是左右各维护一个 heap 就这么简单 每轮看哪边的 top 比较小
要注意的就是一样小时先拿左边的
还有就是边界可以记一下 不要取到重复的
4.竟然是DP... contest时没想出来
主要是没想到机器人的顺序会和工厂的顺序保持一致
也就是如果机器人 r1 < r2 那可以保证最佳解中工厂 f1 <= f2
一样可以讨论每种相对位置的可能性去证明 之前好像有写过类似的概念
总之这样就能从左到右对每个工厂 更新加进(0~工厂容量)个机器人的结果
可以想像成把机器人切成很多块 一块是属于一个工厂
dp[i][j] 代表前i个机器人被配到前j个工厂 并且第j个工厂不能再加入
去 iterate k in range(0~第j+1工厂的容量)
更新 dp[i+k][j+1] = min(dp[i+k][j+1], dp[i][j]+新增的distance)
就是代表第j+1个工厂加入k个机器人 k也可以是0
复杂度是O(机器人数量*工厂数量*工厂容量)
想了很多做法就是没想到DP
有空来把 https://youtu.be/FLbqgyJ-70I 看完好了