企业官网建设流程全解析

做一电影网站怎么赚钱吗,自己做淘宝返利网站,软件开发文档下载,网站建设完成后怎么上传服务器15.交换瓶子 - 蓝桥云课 方法一#xff1a;贪心做法 对于位置 i#xff0c;如果 a[i] ≠ i 就把 a[i] 和 a[a[i]] 交换#xff08;把当前数字放到它应该去的位置#xff09; 这样每次交换都能让至少一个数字归位 重复直到 a[i] i #includeiostream using na…15.交换瓶子 - 蓝桥云课方法一贪心做法对于位置 i如果 a[i] ≠ i就把 a[i] 和 a[a[i]] 交换把当前数字放到它应该去的位置这样每次交换都能让至少一个数字归位重复直到 a[i] i#includeiostream using namespace std; const int N 10010; int n; int a[N]; int main() { cin n; for(int i 1; i n; i) { cin a[i]; } int ans 0; // 贪心直接把每个数放到正确位置 for(int i 1; i n; i) { while(a[i] ! i) { // 如果当前位置的数不对 swap(a[i], a[a[i]]); // 把它和它应该在的位置交换 ans; } } cout ans endl; return 0; }方法二利用环的性质交换排序最小交换问题这个问题实际上可以转化为图论中的环分解问题把排列看作一个置换permutation每个元素应该回到它的正确位置值 i 应该在位置 i通过交换操作我们可以将排列分解为若干个环最小交换次数 所有环的大小之和 - 环的个数#includeiostream #includealgorithm #includecstring using namespace std; const int N 10010; // 题目说 N10000所以开大一点 int n; int a[N]; bool st[N]; // 标记数组记录位置是否访问过 int main() { cin n; for(int i 1; i n; i) // 注意题目瓶子编号从1开始 { cin a[i]; } int ans 0; // 遍历所有位置 for(int i 1; i n; i) { // 如果当前位置的值不是 i且没有被访问过 if(a[i] ! i !st[i]) { // 找到当前元素所在的环 int j i; int cnt 0; // 环的大小 while(!st[j]) { st[j] true; // 标记已访问 j a[j]; // 跳到这个位置应该放的元素的位置 cnt; } // 环的大小为 cnt需要 cnt-1 次交换 ans (cnt - 1); } } cout ans endl; return 0; }