小Why的循环置换
时间限制：1 秒
空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小Why有一个长度为n nn的全排列a aa，定义p x p_xpx表示元素x xx在a aa中的下标。
小Why先将上述n nn个元素映射为图G GG中的点，之后对于每个点x xx，都向p x p_xpx连一条边。在完成这些操作后，图G GG中一共出现了m mm个环（包括自环）。
现在小Why告诉你可以对a aa执行以下操作任意多次：
- 选择a aa中任意两个不同的元素，交换它们的位置。
小Why只打算告诉你n nn和m mm，他想考考你至少需要多少次操作才能使得a aa单调递增。
输入描述
第一行包含两个整数n , m ( 1 ≤ m ≤ n ≤ 10 9 ) n, m\ (1 \le m \le n \le 10^9)n,m(1≤m≤n≤109)，表示图G GG中点的个数和环的个数。
输出描述
输出一个整数，表示最少操作次数。
示例
示例 1
输入：
2 1输出：
1数据范围
- 1 ≤ m ≤ n ≤ 10 9 1 \le m \le n \le 10^91≤m≤n≤109
解题思路
本题是置换环分解 + 贪心的经典问题。给定一个长度为n nn的全排列a aa，定义p x p_xpx为元素x xx在a aa中的下标。图G GG中每个点x xx向p x p_xpx连一条有向边，已知图中共有m mm个环。每次可以交换a aa中任意两个元素的位置，求使a aa单调递增所需的最少交换次数。
1. 问题等价转化
- 全排列a aa中，元素x xx位于位置p x p_xpx。图G GG的边为x → p x x \to p_xx→px。
- 由于p pp是1 ∼ n 1\sim n1∼n的排列，每个点的出度和入度均为1 11，因此图G GG必然由若干个有向环组成。已知环的数量为m mm。
- 当a aa单调递增时，元素x xx必须位于位置x xx，即p x = x p_x=xpx=x。此时图G GG中每个点都是自环，共有n nn个环。
- 因此，目标是将环的数量从m mm增加到n nn。
2. 交换操作对环数的影响
交换a aa中两个位置上的元素，等价于在置换p pp中交换两个元素对应的像。对于置换的环分解：
- 若交换的两个元素位于同一个环中，则该环会分裂成两个环，环数增加1 11；
- 若交换的两个元素位于不同环中，则两个环会合并成一个环，环数减少1 11。
为了使环数尽快增加到n nn，每次应选择同一个环中的两个元素进行交换，使环数增加1 11。
3. 最优次数
- 初始有m mm个环，目标有n nn个环，需要增加n − m n-mn−m个环。
- 每次交换最多使环数增加1 11，因此至少需要n − m n-mn−m次操作。
- 只要存在长度大于1 11的环，就可以通过交换该环中的两个元素将其分裂。重复此过程，经过n − m n-mn−m次操作后，所有环都变成自环，排列a aa变为单调递增。
- 因此最少操作次数恰好为n − m n-mn−m。
4. 算法实现
- 读入n nn和m mm。
- 直接输出n − m n-mn−m。
- 因为n , m ≤ 10 9 n,m\le 10^9n,m≤109，答案在64 6464位整数范围内，无需特殊处理。
5. 复杂度分析
- 时间复杂度：O ( 1 ) O(1)O(1)，仅进行一次减法。
- 空间复杂度：O ( 1 ) O(1)O(1)，仅使用常数个变量。
总结
将排列映射为置换图后，问题转化为通过交换元素将置换的环数从m mm增加到n nn。每次交换同一环中的两个元素可使环数增加1 11，因此最少操作次数为n − m n-mn−m。该方法巧妙利用置换环的性质，将复杂的交换过程抽象为环数的变化，实现极其简洁高效。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;cin>>n>>m;cout<<n-m<<'\n';return0;}
