USACO 2.1.3 Sorting A Three-Valued Sequence 解题报告

首先用两个数组分别保存排了序的数组和没排序的数组，然后再根据这两个判断，当前这个位置上应该是放什么数，而实际上放的是什么数，如果两个位置上需要的都正好是对方所有的，那么这是最好的，进行循环，把所有这种的都交换掉，然后累计交换次数。 但是最后会有这么一种情况，三个位置需要的分别是1, 2, 3，而他们有的分别是3, 1, 2，这时就要交换两次了，而且仔细考虑的话会发现当前面循环完了之后，就只可能剩下这么一种情况了，当然，对数可能不止一对，所以就累计需要的和拥有的不相同的那些，统计起来，处以三再除以二，就是交换次数，结果就出来了。 代码如下： / ID: yylogoo1 PROG: sort3 LANG: C / #include int n; int have[1000]; int need[1000]; int com(void const a, void const b) { return (int )a - (int )b; } int ans; int main(void) { int i, j; freopen("sort3.in", "r", stdin); freopen("sort3.out", "w", stdout); scanf("%d", &n); for(i = 0; i