【uva 10570】Meeting with Aliens(算法效率--暴力+贪心)

时间:2022-02-22 15:51:26

题意:输入1~N的一个排列,每次可以交换2个整数,问使排列变成1~N的一个环状排列所需的虽少交换次数。(3≤N≤500)

解法:(又是一道我没打代码,光想和看就花了很久时间的题~QwQ)由于n很小,可以暴力枚举目标的环状排列,于是贪心交换——把元素 x 直接与它的目标位置上的元素互换,这样至少使1个元素的位置正确了。而若 x 先与其他 k 个元素交换,是最多能得到 k+1 个元素的正确排列的,这样并没有之前的策略优。
    另外,网上关于此题还有一种关于对链状序列找环的说法,我更加不理解。若有人能解释给我听,我会万分感谢的!♪(^∀^●)ノ(这不是说笑的,就算是我AFO了,我也不时会回来看看的。(●`・(エ)・´●)毕竟这些都是自己辛勤耕耘的记录吧,哈哈~)

注意——题目都是先从直接低效的做法想起,再一步步优化的,所以暴力要会!ヽ(=^・ω・^=)丿