现在的位置: 首页 > 综合 > 正文

Sorting A Three-Valued Sequence

2013年01月19日 ⁄ 综合 ⁄ 共 513字 ⁄ 字号 评论关闭

(1)开始只考虑了从第一个元素开始查询,找到每个放置不对的元素nums[i],然后再他应该放置的位置targetP,交换这两个位置的元素,结果没有通过第三个测试

(2)仔细观察了运行的中间状态,发现问题出在当出现这种情况是13222323113的时候,就是说当前最有的交换应该是一种A-B到B-A的,而我遇到的可用的第一个交换位置却产生的是A-B到C-B的结果。

可是我还是做的是一个查找的工作,每次查找可交换点,浪费时间

(3)USACO的解答思路1是:首先找到配对的两个填错的地方(A-B和B-A),这样可以计算出只交换一次就能更正的地方;然后其余的都是需要1-2-3动3个位置,交换两次,因此只要计数还没有放对的位置数目,然后/3*2就得到需要的交换次数。

需要复制一份原来的数组,时间复杂度为O(n^2)

思路2:基本跟我的想法一致

思路3:更加灵巧,根据题目的规则来计算。计算出1、2、3分别的个数,然后计算出,在1中2的个数,3的个数,以此类推。那么

min(2sin1, 1sin2) +min(2sin3, 3sin2) +min(3sin1, 1sin3)

+ 2 * (max(2sin1, 1sin2) - min(2sin1, 1sin2))

抱歉!评论已关闭.