大意:N个外星人围成一桌坐下,有序的排列指N在N-1与N+1中间,现在给出一个序列,问至少交换几次可以得到有序的序列.
思路:不管结果如何,我们可以假设最终的序列是以某个外星人为起点的有序序列,既然如此,我们可以构造另一个序列,把原来的外星人长度增加一倍,这样一来,原序列一定是这个构造序列的子序列.然后通过枚举,可以把最小交换次数求出来.继而解决下一个问题:如何求最小的交换次数?我们可以把1与1号位置的交换,2与2号位置的交换,这样求出的序列即是最小的,这个结论可以记住.然后再反过来求一遍即可,因为题目要求是正,反序列.
该日志由 rhein 于3年前发表在综合分类下,最后更新于 2019年04月06日.