建站培训,全国住房与城乡建设部网站,动易视频网站管理系统,优酷有wordpress插件吗题目#xff1a;
1224. 交换瓶子 - AcWing题库 输入样例1#xff1a;
5
3 1 2 5 4输出样例1#xff1a;
3输入样例2#xff1a;
5
5 4 3 2 1输出样例2#xff1a;
2
思路#xff1a;图论
1.将对应的位置与当前的瓶子序列相连形成环。
2.最少交换次数能形成的最多…题目
1224. 交换瓶子 - AcWing题库 输入样例1
5
3 1 2 5 4输出样例1
3输入样例2
5
5 4 3 2 1输出样例2
2
思路图论
1.将对应的位置与当前的瓶子序列相连形成环。
2.最少交换次数能形成的最多环数n-当前形成的环数cnt 代码
#includecstdio
#includeiostream
using namespace std;
const int N10010;
int b[N];//储存输入的瓶子序列
bool st[N];//判断相应编号的瓶子是否出现过
int cnt;//表示环的数量
int main()
{int n;cinn;for(int i1;in;i)scanf(%d,b[i]);for(int i1;in;i){if(!st[i])//该序列瓶子未出现过{cnt;//环数量1//将同i在同一个环的瓶子序列全部标记for(int ji;!st[j];jb[j])st[j]true;}}//最少交换次数n个数最多能形成的环数-当前环数同环内两瓶子每交换一次环数1coutn-cnt;
}
