#37792: 解題思路(含一些小技巧)


edoctopus322@gmail.com (Moon Jam)

School : 臺北市立成功高級中學
ID : 167591
IP address : [36.225.19.60]
Last Login :
2023-12-23 13:47:18
e465. 置物櫃分配 -- 2018年10月APCS | From: [36.225.24.5] | Post Date : 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)

School : 國立臺灣大學
ID : 252359
IP address : [163.30.63.84]
Last Login :
2024-12-02 12:57:26
e465. 置物櫃分配 -- 2018年10月APCS | From: [42.79.84.251] | Post Date : 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