โปรแกรมหาจำนวนสวอปขั้นต่ำที่จำเป็นในการจัดเรียงถุงเท้าทั้งหมดรวมกันใน C++

สมมติว่าเรามีรายการตัวเลขที่เรียกว่าแถว ซึ่งแสดงถึงถุงเท้าที่วางเรียงกันเป็นแถว ไม่ได้จัดเรียง แต่เราต้องการจัดเรียงใหม่เพื่อให้ถุงเท้าแต่ละคู่อยู่เคียงข้างกัน เช่น (0, 1), (2, 3), (4, 5) เป็นต้น เราต้องหาจำนวนสวอปขั้นต่ำที่จำเป็นในการจัดเรียงใหม่

ดังนั้น หากอินพุตเป็นเหมือนแถว =[0, 5, 6, 2, 1, 3, 7, 4] ผลลัพธ์จะเป็น 2 เนื่องจากลำดับของแถวคือ

• [0, 5, 6, 2, 1, 3, 7, 4]

• [0, 1, 6, 2, 5, 3, 7, 4]

• [0, 1, 3, 2, 5, 6, 7, 4]

• [0, 1, 3, 2, 5, 4, 7, 6]

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

• กำหนดอาร์เรย์ p และอาร์เรย์อื่น sz

• กำหนดฟังก์ชั่น find() สิ่งนี้จะพาคุณ

• return (ถ้า p[u] เหมือนกับ u แล้ว u มิฉะนั้น find(p[u]) และ p[u] :=find(p[u]))

• กำหนดฟังก์ชั่น join() สิ่งนี้จะพา u, v,

• pu :=find((u), pv :=find(v))

• ถ้า pu เหมือนกับ pv แล้ว −

  • กลับ

• ถ้า sz[pu]>=sz[pv] แล้ว −

  • p[pv] :=ปู

  • sz[pu] :=sz[pu] + sz[pv]

• มิฉะนั้น

  • p[pu] :=pv

  • sz[pv] :=sz[pv] + sz[pu]

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• n :=ขนาดของ arr

• p :=อาร์เรย์ขนาด n

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • p[i] :=ฉัน

• sz :=อาร์เรย์ขนาด n และเติม 1

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • u :=arr[i/2] / 2

  • v :=arr[(i/2) OR 1] / 2

  • เข้าร่วม (u, v)

• ตอบ :=0

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า find(i) เหมือนกับ i แล้ว −

    • ans :=ans + sz[i] − 1

  • กลับมาอีกครั้ง

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
vector<int> p, sz;
int find(int u) {
   return p[u] == u ? u : p[u] = find(p[u]);
}
void join(int u, int v) {
   int pu = find(u), pv = find(v);
   if (pu == pv)
   return;
   if (sz[pu] >= sz[pv]) {
      p[pv] = pu;
      sz[pu] += sz[pv];
   }else {
      p[pu] = pv;
      sz[pv] += sz[pu];
   }
}
int solve(vector<int>& arr) {
   int n = arr.size() / 2;
   p = vector<int>(n);
   for (int i = 0; i < n; ++i)
   p[i] = i;
   sz = vector<int>(n, 1);
   for (int i = 0; i < n; ++i) {
      int u = arr[i << 1] / 2;
      int v = arr[i << 1 | 1] / 2;
      join(u, v);
   }
   int ans = 0;
   for (int i = 0; i < n; ++i)
   if (find(i) == i)
   ans += sz[i] − 1;
   return ans;
}
int main(){
   vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4};
   cout << solve(v);
}

อินพุต

{2, 4, 6, 3}

ผลลัพธ์

23