โปรแกรมค้นหาจำนวนสูงสุดของกลุ่มขนาด K ที่มีรายการประเภทที่แตกต่างกันใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า counts โดยที่ counts[i] แทนจำนวนรายการที่เป็นประเภท i เรายังมีค่า k อีกค่าหนึ่ง เราต้องหาจำนวนสูงสุดของกลุ่มขนาด k ที่เราหาได้ เพื่อให้แต่ละกลุ่มมีรายการประเภทที่แตกต่างกัน

ดังนั้น หากอินพุตเท่ากับจำนวน =[2, 3, 5, 3] k =2 ผลลัพธ์จะเป็น 6 เพราะให้รายการสี่ประเภทแสดงด้วย a, b, c, d ตามลำดับ เราสามารถมีกลุ่มต่อไปนี้ของ k =2 โดยที่องค์ประกอบทั้งหมดมีประเภทที่แตกต่างกัน:[(c, a), (b, a), (c, b), (c, b), (d, a), (ง, ก)].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดฟังก์ชันที่เป็นไปได้ () นี้จะใช้เวลานับกลุ่ม k
จำเป็น :=กลุ่ม * k
สำหรับ i ในช่วง 0 ถึงขนาดของการนับ ทำ
- อุณหภูมิ :=จำนวนขั้นต่ำ[i] กลุ่ม และที่จำเป็น
- จำเป็น :=จำเป็น - ชั่วคราว
- ถ้าจำเป็นเท่ากับ 0 แล้ว
  - คืนค่า True
คืนค่าเท็จ
กำหนดฟังก์ชัน Solve() นี้จะใช้เวลานับ k
res :=0
l :=0
r :=ผลรวมขององค์ประกอบทั้งหมดที่มีอยู่ในการนับ
ในขณะที่ l <=r ทำ
- m :=l + floor of (r - l) / 2
- ถ้าเป็นไปได้(นับ m k) เป็นจริง แล้ว
  - l :=m + 1
  - res :=สูงสุดของ res และ m
- มิฉะนั้น
  - r :=m - 1
ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def possible(counts, groups, k):
   required = groups * k
   for i in range(len(counts)):
      temp = min(counts[i], groups, required)
      required -= temp
      if required == 0:
         return True
   return False

def solve(counts, k):
   res = 0
   l = 0
   r = sum(counts)
   while l <= r:
      m = l + (r - l) // 2
      if possible(counts, m, k):
         l = m + 1
         res = max(res, m)
      else:
         r = m - 1
   return res

counts = [2, 3, 5, 3]
k = 2
print(solve(counts, k))

อินพุต

[2, 3, 5, 3], 2