小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;}