發表新討論
#37792: 解題思路（含一些小技巧）


edoctopus322@gmail.com (Moon Jam)

學校 : 臺北市立成功高級中學
編號 : 167591
來源 : [36.225.19.60]
最後登入時間 ：
2023-12-23 13:47:18
e465. 置物櫃分配 -- 2018年10月APCS | From: [36.225.24.5] | 發表日期 : 2023-10-08 15:32
 
解題思路：
這題我的做法是先整理出哪些櫃子數量可以由數個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 (Andy)

學校 : 國立臺灣大學
編號 : 252359
來源 : [163.30.63.65]
最後登入時間 ：
2024-11-11 10:00:57
e465. 置物櫃分配 -- 2018年10月APCS | From: [42.79.84.251] | 發表日期 : 2023-12-21 10:06
 
解題思路：
這題我的做法是先整理出哪些櫃子數量可以由數個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