AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

比较奇妙思路的算法题总结(间歇性补充)

作者: 作者的头像   歪嘴战神叁叁叁 ,  2020-02-05 23:24:20 ,  所有人可见 ,  阅读 627


3


置换群 环

  1. 交换瓶子
    有 N 个瓶子,编号 1∼N,放在架子上。

比如有 5 个瓶子:

2 1 3 5 4
要求每次拿起 2 个瓶子,交换它们的位置。

经过若干次后,使得瓶子的序号为:

1 2 3 4 5
对于这么简单的情况,显然,至少需要交换 2 次就可以复位。

如果瓶子更多呢?你可以通过编程来解决。

输入格式
第一行包含一个整数 N,表示瓶子数量。

第二行包含 N 个整数,表示瓶子目前的排列状况。

输出格式
输出一个正整数,表示至少交换多少次,才能完成排序。

数据范围
1≤N≤10000,

输入样例1:
5
3 1 2 5 4
输出样例1:
3
输入样例2:
5
5 4 3 2 1
输出样例2:
2

本题特点:

比如 
节点 3 1 2 5 4
位置 1 2 3 4 5
y总讲的是通过位置映射节点形成的环(反过来看也是一样的)
上面的数列有两个环(1的位置是3,3的位置是2,2的位置是1,1的位置又是3 故形成一个环) 3 -> 2 -> 1 -> 3,
同理另一个环为 5 -> 4 -> 5;

有两种情况(性质):
    情况一:
        交换同一个环内的点可以分裂成两个环 例如交换节点 
        3 和 1,那么位置1的节点就变成了1,而位置2的节点就
        变成了3,根据 通过位置映射节点形成的环就会将一个环
        形成了1 -> 1,3 -> 2 -> 3 两个环
    情况二:
            交换不同环中的点可以合并两个环

    本题解题思路:如果有k个环在n个位置上边,如果想形成n个环(n个环意思就是每个节点都是一个自己和自己相连的自闭环),根据情况一,如果想分裂成n个环就最少分裂 n-k 次,本题即解

复杂度O(n)

#include<iostream>

using namespace std;
const int N = 10000 + 10;
int a[N];
bool st[N];
int main(){
    int n;
    cin >> n;

    for(int i = 1;i <= n;i++) cin >> a[i];

    int cnt = 0;
    for(int i = 1;i <= n;i++){
        if(!st[i]){
            cnt ++;
            for(int j = i;!st[j];j = a[j])
            st[j] = true;
        }
    }

    cout << n - cnt << endl;

    return 0;

}

个人思路代码O(n^2)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int N = 10000 + 10;

int a[N],b[N];

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
      cin >> a[i];
    } 
    int res = 0;
    for(int i = 1;i <= n;i++){
        if(i != a[i]){
            for(int j = 1;j <= n;j++){
                if(i == a[j]){
                    swap(a[i],a[j]);
                    res++;
                }

            }
        }
    }
    cout << res;
    return 0;


}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息