题解 P1459 【三值的排序 Sorting a Three-Valued Sequence】

zhouwc

2017-08-27 18:02:27

Solution

#Pascal 看到写此题题解的大神众多,于是心血来潮(虽然我的水平不高) 对于这一道题来说,我的算法是这样的(在我的程序中就不一一说明了): 首先,我先在b数组中把正确的序列给排列出来,方便接下来的比较。 ###第一次扫描(这里用x,y两个数) 如果找到x与y两个数交换位置后,两个数都可以到正确的位置,那么就进行交换。 ###第二次扫描(这里用x,y两个数) 如果找到x与y两个数交换位置后,其中的1个数可以到正确的位置,那就进行交换。 在两次扫描后,便可以输出正确的解 下面附上pascal AC 代码 ```cpp var n,i,j,k,t:longint; a,b:array[1..1001]of longint; l:array[1..3]of longint; begin readln(n); for i:=1 to n do begin readln(a[i]); if a[i]=1 then l[1]:=l[1]+1; if a[i]=2 then l[2]:=l[2]+1; if a[i]=3 then l[3]:=l[3]+1; end; for i:=1 to l[1] do b[i]:=1; for i:=l[1]+1 to l[1]+l[2] do b[i]:=2; for i:=l[1]+l[2]+1 to n do b[i]:=3; for i:=1 to n-1 do for j:=i+1 to n do if (a[i]<>b[i]) and (a[j]<>b[j]) and (a[j]=b[i]) and (a[i]=b[j]) then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; k:=k+1; end; for i:=1 to n-1 do for j:=i+1 to n do if (a[i]<>b[i]) and (a[j]<>b[j]) and ((a[j]=b[i]) or (a[i]=b[j])) then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; k:=k+1; end; writeln(k); end. ``` 如有错误,还请指出。