สมมติว่าเรามีค่า batchSize และกลุ่มอาร์เรย์โดยที่ groups[i] แสดงว่ามีกลุ่มลูกค้ากลุ่มหนึ่ง[i] ที่จะมาที่ร้าน ดังนั้นจึงมีร้านโดนัทที่อบโดนัทเป็นชุดตามขนาดที่กำหนด แต่พวกเขามีกฎข้อเดียวคือ พวกเขาต้องเสิร์ฟโดนัททั้งหมดในกลุ่มก่อนที่จะเสิร์ฟโดนัทในชุดถัดไป และลูกค้าแต่ละคนจะได้รับโดนัทหนึ่งชิ้นพอดี เมื่อกลุ่มเข้ามาในร้าน ลูกค้าทุกคนในกลุ่มนั้นจะต้องได้รับบริการก่อนจะพูดถึงกลุ่มต่อไป กลุ่มหนึ่งอาจมีความสุขถ้าทุกคนได้โดนัทสดใหม่ (กล่าวคือ ลูกค้ารายแรกของกลุ่มไม่รับโดนัทที่หลงเหลือจากกลุ่มที่แล้ว)
เราสามารถจัดเรียงกลุ่มใหม่ได้ และสุดท้ายเราต้องหากลุ่มที่มีความสุขให้ได้มากที่สุดหลังจากจัดเรียงกลุ่มใหม่แล้ว
ดังนั้น ถ้าอินพุตเป็นเหมือน batchSize =4 กลุ่ม =[2,1,8,4,3] ผลลัพธ์จะเป็น 4 เพราะเราสามารถจัดเรียงใหม่ได้เช่น [8,4,2,3,1] ก่อน กลุ่มที่สอง สาม และสี่มีความสุข เราสามารถทำโดนัทสองชุดสำหรับกลุ่มแรก ชุดหนึ่งสำหรับกลุ่มที่สอง และชุดหนึ่ง จากนั้นจึงส่งไปยังกลุ่มที่สามและอีกชุดสำหรับกลุ่มที่สี่
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
l :=รายการที่มี (g mod batchSize) สำหรับ g ทั้งหมดในกลุ่ม
-
count :=แผนที่ที่มีความถี่ขององค์ประกอบของ l
-
g :=รายการ count[i] สำหรับ i ทั้งหมดในช่วง 0 ถึง batchSize
-
กำหนดฟังก์ชัน dp() นี่จะใช้เวลา sm, t
-
ถ้าค่าสูงสุดของ t เท่ากับ 0 แล้ว
-
คืนค่า 0
-
-
ตอบ :=0
-
arr :=t
-
สำหรับ k ในช่วง 0 ถึง batchSize - 1 ทำ
-
ถ้า arr[k] เหมือนกับ 0 แล้ว
-
ไปทำซ้ำต่อไป
-
-
arr[k] :=arr[k] - 1
-
ans :=สูงสุดของ ans และ dp((sm + k) mod batchSize, arr)
-
arr[k] :=arr[k] + 1
-
-
คืนค่า ans +(1 ถ้า sm เหมือนกับ 0 มิฉะนั้น 0)
-
จากวิธีหลักส่งคืน dp(0, g)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
from collections import Counter
def solve(batchSize, groups):
l = [g % batchSize for g in groups]
count = Counter(l)
g = [count[i] for i in range(batchSize)]
def dp(sm, t):
if max(t) == 0:
return 0
ans, arr = 0, list(t)
for k in range(batchSize):
if arr[k] == 0:
continue
arr[k] -= 1
ans = max(ans, dp((sm + k) % batchSize, arr))
arr[k] += 1
return ans + (sm == 0)
return dp(0, g)
batchSize = 4
groups = [2,1,8,4,3]
print(solve(batchSize, groups)) อินพุต
4, [2,1,8,4,3]
ผลลัพธ์
4
