เกมพลิกไพ่ใน C++

สมมติว่าบนโต๊ะมีการ์ด N โดยพิมพ์จำนวนเต็มบวกที่ด้านข้างของการ์ดแต่ละใบ (อาจแตกต่างกัน) เราต้องพลิกไพ่จำนวนเท่าใดก็ได้ และหลังจากที่เราเลือกไพ่หนึ่งใบ หากหมายเลข X ที่ด้านหลังของการ์ดที่เลือกไม่ได้อยู่ด้านหน้าของการ์ดใดๆ แสดงว่าหมายเลข X นั้นเรียกว่าดี เราต้องหาจำนวนที่น้อยที่สุดที่ดีหรือไม่? เมื่อตัวเลขไม่ดี ให้คืนค่า 0 ในที่นี้ fronts[i] และ backs[i] แทนหมายเลขที่ด้านหน้าและด้านหลังของการ์ด i การพลิกจะสลับตัวเลขด้านหน้าและด้านหลัง ดังนั้นค่าที่อยู่ด้านหน้าจึงอยู่ที่ด้านหลังและกลับกัน

ดังนั้นหากอินพุตเป็นเหมือน fronts =[1,2,4,4,7] และ backs =[1,3,4,1,3] ผลลัพธ์จะเป็น 2 ดังนั้นหากเราพลิกไพ่ใบที่สอง มูลค่าด้านหน้าจะเป็น [1,3,4,4,7] และด้านหลังจะเป็น [1,2,4,1,3] เราจะเลือกไพ่ใบที่สองซึ่งมีหมายเลข 2 อยู่ด้านหลังและไม่ได้อยู่หน้าไพ่ใด ๆ ดังนั้น 2 จึงเป็นตัวเลขที่ดี

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

• กำหนดชุด s, n :=ขนาดของ fronts, ret :=inf
• สำหรับ i ในช่วง 0 ถึง n – 1
  • ถ้า fronts[i] =back[i] ให้ใส่ fronts[i] เข้าไปใน s
• สำหรับ i ในช่วง 0 ถึง n – 1
  • ถ้า fronts[i] อยู่ใน set แล้ว ret :=ขั้นต่ำของ ret และ fronts[i]
• สำหรับ i ในช่วง 0 ถึง n – 1
  • ถ้า backs[i] ไม่อยู่ใน set แล้ว ret :=ขั้นต่ำของ ret และ backs[i]
• คืนค่า 0 เมื่อ ret =inf มิฉะนั้น ret

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int flipgame(vector<int>& fronts, vector<int>& backs) {
      set <int> s;
      int n = fronts.size();
      int ret = INT_MAX;
      for(int i = 0; i < n; i++){
         if(fronts[i] == backs[i])s.insert(fronts[i]);
      }
      for(int i = 0; i <n; i++ ){
         if(s.count(fronts[i]) == 0) ret = min(ret, fronts[i]);
      }
      for(int i = 0; i <n; i++ ){
         if(s.count(backs[i]) == 0) ret = min(ret, backs[i]);
      }
      return ret == INT_MAX? 0 : ret;
   }
};
main(){
   vector<int> v1 = {1,2,4,4,7};
   vector<int> v2 = {1,3,4,1,3};
   Solution ob;
   cout << (ob.flipgame(v1, v2));
}

อินพุต

[1,2,4,4,7]
[1,3,4,1,3]

ผลลัพธ์

2