ZJYYCOJ 好基友（贪心/并查集）

• 题面描述
  每个班级总有几对好基友，创意班也不例外，最典型的就是汪李弟弟组合。现在有N对基友随机的坐在一排连续的座位上，好基友们总是希望能坐在一起，现在请你帮帮忙，计算一下最少要交换多少次（每两个人交换一次位置算作1次），以便让每对好基友都并肩坐在一起。
  人的编号为 0 —— 2N - 1
  座位的编号为 0 —— 2N - 1
  每对好基友按照编号顺序来确定，（4，5）为好基友，（8，9）为好基友 ， （0，1）为好基友

• 输入
  样例输入由多组测试样例组成，第一行输入一个整数N（1 <= N <= 100000），代表有N对基友。第二行输入2N个整数，代表每个位置初始上的人编号

• 输出
  输出最少交换次数

• 样例输入

• 样例输出

• 1
  0

• 解题思路(偷懒使用官方解题思路啦)

贪心代码

#include <bits/stdc++.h>

using namespace std;
int a[200005], pos[200005];

int main()
{
	int n;
	while(~scanf("%d", &n))
	{
		int sum = 0;  // 交换次数
		for(int i = 1; i <= 2 * n; i++)
		{
			scanf("%d", &a[i]);
			pos[a[i]] = i;  // 记录每个同学的位置
		}
		for(int i = 1; i <= 2 * n; i += 2)
		{
			int temp = a[i] ^ 1;  // 第i个位置的基友
//			cout << temp << endl;
			if(a[i + 1] != temp)
			{
				a[pos[temp]] = a[i + 1];  // 序号互换
				a[i + 1] = temp;
				pos[a[pos[temp]]] = pos[temp];  // 位置互换
				pos[temp] = i + 1;
				sum++;
			}
		}
		printf("%d\n", sum);
	}
	return 0;
 } 

贪心这里还是WA了两次，是因为只交换了两个位置上的两个序号但没有交换这两个序号的位置。

并查集代码

#include <bits/stdc++.h>

using namespace std;
int fa[200005], sum[200005], a[200005];
int findx(int r)
{
   int temp, k = r;
   while(r != fa[r])
   	r = fa[r];
   //路径压缩
   while(k != r)
   {
   	temp = fa[k];
   	fa[k] = r;
   	k = temp;
   }
   return r;
}
void merge(int x, int y)
{
   int xx = findx(x), yy = findx(y);
   if(xx != yy)
   	fa[xx] = yy;
}

int main()
{
   ios::sync_with_stdio(false);
   int n, ans;
   while(cin >> n)
   {
   	ans = 0;
   	memset(sum, 0, sizeof(sum));
   	for(int i = 0; i < 2 * n; i++)
   		fa[i] = i;
   	for(int i = 0; i < 2 * n; i++)
   	{
   		cin >> a[i];
   		if(i % 2)
   		{
   			merge(i, i - 1);  // 合并基友
   			merge(a[i], a[i - 1]);  // 合并一个沙发上的同学
   		}
   	}
   	int temp;
   	for(int i = 0; i < 2 * n; i++)
   	{
   		temp = findx(i);
   		sum[temp]++;  // 将所有同学统计到同一个环的祖先上用于计算
   	}
   	for(int i = 0; i < 2 * n; i++)
   	{
   		if(sum[i])
   			ans += (sum[i] / 2 - 1);  // 同一个换需要交换(sum[i] / 2 - 1)次
   	}
   	cout << ans << endl;
   }
   return 0;
}