โปรแกรมนับจำนวนเพื่อนที่ไม่มีความสุขใน Python

สมมติว่าเรามีรายการความชอบสำหรับเพื่อน n(คน) ที่แตกต่างกัน สำหรับแต่ละบุคคล i การตั้งค่า [i] จะเก็บรายชื่อเพื่อนที่จัดเรียงตามความชอบ ดังนั้น เพื่อนที่อยู่ในรายชื่อก่อนจึงเป็นที่ต้องการมากกว่าเพื่อนที่อยู่ในรายชื่อ เพื่อนในแต่ละรายการจะมีเลขจำนวนเต็มตั้งแต่ 0 ถึง n-1 เพื่อนทุกคนถูกแบ่งออกเป็นคู่ที่แตกต่างกัน โดยที่ pairs[i] =[xi, yi] แทน xi จับคู่กับ yi และ/หรือ yi จับคู่กับ xi แต่เพื่อน x จะไม่มีความสุขถ้า x จับคู่กับ y และมีเพื่อน u ที่จับคู่กับ v ด้วย แต่ -

• x ชอบคุณมากกว่า y และ
• คุณชอบ x มากกว่า v.

เราต้องหาจำนวนเพื่อนที่ไม่มีความสุข

ดังนั้น หากอินพุตเหมือนกับการตั้งค่า =[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] คู่ =[[0, 1] , [2, 3]] จากนั้นผลลัพธ์จะเป็น 2 เพราะเพื่อนคนแรกไม่มีความสุขเพราะคนที่ 1 จับคู่กับคนที่ 0 แต่ชอบคนที่ 3 มากกว่าคนที่ 0 และคนที่ 3 ชอบคนที่ 1 มากกว่าคนที่ 2 และเพื่อนที่ 3 ไม่มีความสุข เพราะคนที่ 3 ถูกจับคู่กับคนที่ 2 แต่ชอบคนที่ 1 มากกว่า 2 และคนที่ 1 ชอบคนที่ 3 มากกว่า 0

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

• กราฟ :=รายการที่อยู่ติดกันเพื่อสร้างกราฟ โดยเริ่มแรกว่างเปล่า
• สำหรับแต่ละคู่ (s, e) เป็นคู่ ทำ
  • สำหรับแต่ละรูปแบบในการตั้งค่า[s] ทำ
    • ถ้า pref เหมือนกับ end แล้ว
      • ออกมาจากลูป
    • กราฟ[s, pref] :=1
  • สำหรับแต่ละรูปแบบในการตั้งค่า[e], ทำ
    • ถ้า pref เหมือนกับ start แล้ว
      • ออกมาจากลูป
    • กราฟ[e, pref] :=1
• ไม่มีความสุข :=0
• สำหรับแต่ละคู่ (s, e) เป็นคู่ ทำ
  • สำหรับแต่ละรูปแบบในกราฟ[s] ทำ
    • ถ้า graph[pref][s] ไม่ว่างเปล่า
      • ไม่พอใจ :=ไม่มีความสุข + 1
      • ออกมาจากลูป
  • สำหรับแต่ละรูปแบบในกราฟ[end] ทำ
    • ถ้า graph[pref][e] ไม่ว่างเปล่า
      • ไม่พอใจ :=ไม่มีความสุข + 1
      • ออกมาจากลูป
• กลับมาอย่างไม่มีความสุข

ตัวอย่าง

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

from collections import defaultdict
def solve(preferences, pairs):
   graph = defaultdict(dict)
   for start, end in pairs:
      for pref in preferences[start]:
         if pref == end:
            break
         graph[start][pref] = 1
      for pref in preferences[end]:
         if pref == start:
            break
         graph[end][pref] = 1

   unhappy = 0

   for start, end in pairs:
      for pref in graph[start]:
         if graph[pref].get(start, None):
            unhappy += 1
            break
      for pref in graph[end]:
         if graph[pref].get(end, None):
            unhappy += 1
            break
   return unhappy

preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]]
pairs = [[0, 1], [2, 3]]
print(solve(preferences, pairs))

อินพุต

[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], [[0, 1], [2, 3]]

ผลลัพธ์

2