小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_xxpx​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。该方法巧妙利用置换环的性质将复杂的交换过程抽象为环数的变化实现极其简洁高效。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;cinnm;coutn-m\n;return0;}