程序查找在C ++中将所有袜子组合在一起所需的最少交换次数

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个称为row的数字列表，它表示连续排的袜子。它们没有排序，但是我们要重新排列它们，以便每对袜子并排放置，例如(0,1)，(2,3)，(4,5)，依此类推。我们必须找到重新安排交换所需的最少数量。

因此，如果输入像row = [0，5，6，2，1，1，3，7，4]，则输出将为2，因为行顺序为

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

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

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

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

为了解决这个问题，我们将遵循以下步骤-

  • 定义一个数组p和另一个数组sz

  • 定义一个函数find()，它将花费你，

  • 返回（如果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]：= pu

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

  • 除此以外

    • p [pu]：= pv

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

  • 从主要方法中执行以下操作-

  • n：= arr的大小

  • p：=大小为n的数组

  • 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

    • p [i]：= i

  • sz：=大小为n的数组，并用1填充

  • 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

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

    • v：= arr [（i / 2）OR 1] / 2

    • join(u, v)

  • 回答：= 0

  • 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

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

    • 如果find(i)与i相同，则-

    • 返回ans

让我们看下面的实现以更好地理解-

示例

#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

以上是 程序查找在C ++中将所有袜子组合在一起所需的最少交换次数 的全部内容， 来源链接： utcz.com/z/345258.html

回到顶部