1224.交换瓶子
贪心:
每个瓶子和序号对应情况有两种:
- 对应,对应的时候,直接就符合要求,不需要交换
- 不对应-如果不对应的话,我们应该交换到当前位置对应。
问题来到,如果不对应的话,怎么交换才是最优的?
因为瓶子的序号是一个序列,所以如果当前瓶子的不对应当前的序号,那么当前的瓶子对应的序号和它的瓶子也一定不对应。
比如:
显然当我们遍历到1的时候,我们并不知道,对应1的瓶子在哪里,我们只知道当前不符合的瓶子对应到哪里。所以我们可以一直将当前位置的瓶子,和它应该在的位置交换,这样每一次交换,至少有一个瓶子到达了它应该在的位置,直到当前位置对应为止。
为什么这样是最优的呢?
因为如果一个瓶子和序号不对应,最少需要一次将它和应该在的位置交换,而我们的交换方法就满足每次交换至少有一个瓶子到达了它应该在的位置。
实现:
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5;
int a[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int res = 0;
for (int i = 1; i <= n; i++)
while (i != a[i])
{
swap(a[i], a[a[i]]);
res++;
}
printf("%d\n", res);
return 0;
}
置换群:
我们先通过画图,将当前瓶子和想交换的瓶子连在一起:
(因为3号瓶子要到达3这个位置,所以想要和2号瓶子交换,下面同理:)
因为我们最终想要所有瓶子复位,那么当当前瓶子想交换的位置是自己的位置的时候,就说明该瓶子复位了。
我们可以交换两个位置来看一下:
可以发现,如果一个环中的点数是$k$,那么进行$k-1$次交换就可以使环内所有瓶子复位。
那么可以得出,需要交换的总次数,是$n的个数-环的个数$。
为什么这样是最优的呢?
因为每次交换,至少可以使得一个瓶子想和自己交换(即该瓶子复位)。
实现:
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5;
int a[N], vis[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int cnt = 0;
for (int i = 1; i <= n; i++)
//如果该点不被之前的环包括,则则从它开始必有一环
if (!vis[i])
{
cnt++;
//将环上所有点都标记上
for (int j = a[i]; !vis[j]; j= a[j])
vis[j] = 1;
}
printf("%d\n", n - cnt);
return 0;
}
就喜欢这样清晰明了的解题思路
写的真好
写的真好