#37792: 解題思路（含一些小技巧）
edoctopus322@gmail.com
(Moon Jam)
學校
:
臺北市立成功高級中學
編號 : 167591
來源 : [36.225.19.60]
最後登入時間 ：
2023-12-23 13:47:18
解題思路：
這題我的做法是先整理出哪些櫃子數量可以由數個x相加而成，然後再找大於等於需要櫃子量的最小值，不過這樣依照題目給定的N、M範圍應該是過不了的，在最糟狀況下會是$O(N^2+M)$，只是試了之後是可以AC的，後來看別人的解法是用01背包問題解，但也會到$O(MN)$，如果這題要過應該是比較像中一中judge上的這題，不過輸入順序不同，需要稍微修改。
🌟題目給的S是需要的空櫃子，但事實上那些人要給你的數量只有S-(M-total_x)，total_x表示所有x的和，也就是說，如果S-(M-total_x)是負的，那就代表你不需要請人退櫃子，因為你已經有足夠的空櫃子了，而當正的時候，就是你需要請人退櫃子的數量。
#38745: Re: 解題思路（含一些小技巧）
bobobo0413
(杜拜、慕尼黑、蘇黎世、清邁、東京、首爾、布拉格)
學校
:
國立臺灣大學
編號 : 252359
來源 : [42.76.162.171]
最後登入時間 ：
2024-04-13 18:42:54
解題思路：這題我的做法是先整理出哪些櫃子數量可以由數個x相加而成，然後再找大於等於需要櫃子量的最小值，不過這樣依照題目給定的N、M範圍應該是過不了的，在最糟狀況下會是$O(N^2+M)$，只是試了之後是可以AC的，後來看別人的解法是用01背包問題解，但也會到$O(MN)$，如果這題要過應該是比較像中一中judge上的這題，不過輸入順序不同，需要稍微修改。
🌟題目給的S是需要的空櫃子，但事實上那些人要給你的數量只有S-(M-total_x)，total_x表示所有x的和，也就是說，如果S-(M-total_x)是負的，那就代表你不需要請人退櫃子，因為你已經有足夠的空櫃子了，而當正的時候，就是你需要請人退櫃子的數量。
你說的兩題是一樣的，不過我覺得這題有點難耶
ZeroJudge Forum