跳至正文

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

发表回复

您的电子邮箱地址不会被公开。