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 看完好了