并查集问题
★问题描述皮卡丘一共有N只袜子，袜子共有K种颜色(当然一只袜子只有一种颜色)（K<=N）。爱卫生的皮卡丘在连续M天中每天都要穿两只颜色相同的袜子，如果皮卡丘某天拿到了两只颜色不同的袜子，它就会施展魔法改变袜子颜色使得两只袜子变成相同颜色。
现给出皮卡丘在M天内每天要穿的两只袜子的序号，问它最少需要修改几只袜子的颜色才能达到目的。
★数据输入
输入第一行包括三个正整数 N，M，K（2<=N<=200000，0<=M<=200000,1<=K<=200000）。
第二行输入 N 个正整数 C1,C2,C3...CN(1<=Ci<=K)，表示每只袜子的颜色。
接下来M行，每行两个正整数 li，ri (1<=li,ri<=N) 表示皮卡丘在M天内每天要穿的袜子序号。
★数据输出
输出一个整数，为皮卡丘需要修改颜色的袜子的最少只数。
★输入示例
323
123
12
23
★输出示例
2 你这个文字讲的太难理解了
现给出皮卡丘在M天内每天要穿的两只袜子的序号，问它最少需要修改几只袜子的颜色才能达到目的
每天穿两个袜子不同颜色只要施展魔法变一次就变成相同颜色了？你所说的目的是什么》？是所有的袜子要全部变成一样的目的还是每天变变多少天吗？ zy8818 发表于 2021-11-13 20:19
你这个文字讲的太难理解了
现给出皮卡丘在M天内每天要穿的两只袜子的序号，问它最少需要修改几只袜子的颜 ...
就是比如 第一天穿 1 2第二天穿 1 2 那只要第一天把序号1的袜子颜色改成颜色 2 那第二天就不用改了,只修改了一次 本帖最后由 傻眼貓咪 于 2021-11-14 11:55 编辑
题目看似简单，实则困难：
思路
首先，假设某天袜子颜色不一，必须解决该改变的袜子颜色（2 选 1），如同题目要求，以最少改变次数作答（虽然每次 2 选 1，但该选择哪里一个袜子，最终都会大大影响全局袜子变数）
其二，范本太大，每项少于 200000，如果可以直接以组合公式算还好，但这题目给定每日袜子颜色不定，变数超级大，无论是内存空间，时间复杂度都大大提升
注：一般这种题目，除非数学超级好，否则大佬们都会视而不见，毕竟数学和程序代码是 2 个不同领域的学问 #include <bits/stdc++.h>
using namespace std;
const int veryBig=200005;
vector<int> Boss;
int Function;
int Amazing;
int wanting(int Value) {
if ( Value != Function )
{
Function = wanting( Function );
}
return Function;
}
void Unity(int first,int second) {
int A = wanting(first);
int B = wanting(second);
if (A != B)
{
Function = A;
}
}
void Play()
{
int Number;
int Days;
int Color;
int Left;
int Right;
int total;
cin >> Number >> Days >> Color;
for (int i = 1; i <= Number; i++) {
Function = i;
cin >> Amazing;
}
for (int i = 1; i <= Days; i++) {
cin >> Left >> Right;
Unity(Left,Right);
}
for (int i = 1; i <= Number; i++) {
Boss.push_back(Amazing);
}
for (int i = 1; i <= Number; i++) {
int Length;
Length = Boss.size();
int Max;
Max = 0;
if (Length > 1) {
map <int,int> sum;
for (int j = 0; j<Length; j++) {
sum]++;
Max = max( Max, sum]);
}
total += ( Length - Max );
}
Boss.clear();
}
cout << total;
}
int main() {
Play();
} 1248762042 发表于 2021-11-16 19:40
写出来了
页:
[1]