Chương trình đếm số bạn bè không hạnh phúc bằng Python

Giả sử chúng ta có một danh sách sở thích cho n (chẵn) những người bạn khác nhau. Đối với mỗi người tôi, sở thích [i] chứa danh sách bạn bè được sắp xếp theo thứ tự ưu tiên. Vì vậy, một người bạn sớm hơn trong danh sách được ưu tiên hơn một người bạn sau đó trong danh sách. Bạn bè trong mỗi danh sách được đánh số bằng các số nguyên từ 0 đến n-1. Tất cả những người bạn được chia thành các cặp khác nhau. trong đó các cặp [i] =[xi, yi] biểu thị xi được ghép nối với yi và / hoặc yi được ghép nối với xi. Nhưng một người bạn x sẽ không vui nếu x kết đôi với y và tồn tại một người bạn u cũng ghép với v nhưng -

• x thích bạn hơn y và
• u thích x hơn v.

Chúng ta phải tìm số lượng những người bạn không hạnh phúc.

Vì vậy, nếu đầu vào giống như tùy chọn =[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] cặp =[[0, 1] , [2, 3]], thì đầu ra sẽ là 2 vì người bạn đầu tiên không hài lòng vì người 1 được ghép với người 0 nhưng thích người 3 hơn người 0 và người 3 thích người 1 hơn người 2. Và người bạn 3 không hài lòng vì người 3 được ghép với người 2 nhưng thích người 1 hơn người 2 và người 1 thích người 3 hơn người 0.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• graph:=một danh sách gần kề để tạo biểu đồ, lúc đầu trống
• đối với mỗi (s, e) theo cặp, thực hiện
  • đối với mỗi pref trong [s] tùy chọn, hãy thực hiện
    • nếu pref giống với end, thì
      • ra khỏi vòng lặp
    • graph [s, pref]:=1
  • đối với mỗi pref trong tùy chọn [e], thực hiện
    • nếu pref giống như start, thì
      • ra khỏi vòng lặp
    • graph [e, pref]:=1
• không vui:=0
• đối với mỗi (s, e) theo cặp, thực hiện
  • đối với mỗi pref trong [s] biểu đồ, hãy thực hiện
    • nếu graph [pref] [s] không trống, thì
      • không vui:=không vui + 1
      • ra khỏi vòng lặp
  • đối với mỗi pref trong biểu đồ [end], hãy thực hiện
    • nếu graph [pref] [e] không trống, thì
      • không vui:=không vui + 1
      • ra khỏi vòng lặp
• trả lại không vui

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

 từ bộ sưu tập nhập defaultdictdef giải quyết (tùy chọn, cặp):graph =defaultdict (dict) cho bắt đầu, kết thúc theo cặp:cho pref trong tùy chọn [start]:if pref ==end:break graph [start] [pref] =1 cho pref trong tùy chọn [end]:if pref ==start:break graph [end] [pref] =1 không hài lòng =0 cho bắt đầu, kết thúc theo cặp:cho pref trong graph [start]:if graph [pref] .get (bắt đầu, Không có):không vui + =1 ngắt cho pref trong biểu đồ [end]:nếu biểu đồ [pref] .get (kết thúc, Không):không vui + =1 ngắt trả lại không vuipreferences =[[1, 2, 3], [ 3, 2, 0], [3, 1, 0], [1, 2, 0]] cặp =[[0, 1], [2, 3]] print (giải quyết (tùy chọn, cặp))  
 Đầu vào 
 
 [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], [[0, 1], [2, 3]] 
 
 Đầu ra 
 
 2