【题意】
有n(n<=10000)头脾气不同的牛,给出他们的脾气(0<=脾气值<=100000,且都不相同),交换两头牛的位置所需代价为两头牛的脾气值之和,求将序列变为升序序列的最小代价
【输入】
第一行一个n
接下来n行每行一个数字表示该头牛的脾气值
【输出】
一个数字,表示将序列变为升序序列的最小代价
黑书P248有讲
因为脾气不相同,所以每头牛都有它固定的位置,站在他固定位置的牛也有其固定位置,所以就出现了一个循环
对于一个长度为l循环想要让其变为有序,若只考虑循环内元素交换,需要交换l-1次,理所应当的,我们选取其中最小的元素与其他的逐一交换,代价为sum+(l-2)*(循环中最小值)
除此之外还有另一种交换方式,就是借助序列中最小的值跟序列中最小值交换,代替最小值进行交换,这样有可能更优,所需代价为sum+(循环中最小值)+(l+1)*(序列中最小值)
二者取优求和即可
program poj3270; var n,i,j,k,l:longint; sum,temp,min,ans:int64; p,dl:array [0..10001] of longint; yes:array [0..10001] of boolean; point:array [0..100001] of longint; procedure swap (var a,b:longint); var i:longint; begin i:=a; a:=b; b:=i; end; procedure qsort (s,e:longint); var i,j,k:longint; begin if s>=e then exit; i:=s; j:=e; k:=p[dl[(s+e) div 2]]; while i<=j do begin while p[dl[i]]<k do inc(i); while p[dl[j]]>k do dec(j); if i>j then break; swap(dl[i],dl[j]); inc(i); dec(j); end; qsort(s,j); qsort(i,e); end; begin read(n); min:=maxlongint; for i:=1 to n do begin read(p[i]); if p[i]<min then min:=p[i]; end; for i:=1 to n do dl[i]:=i; qsort(1,n); for i:=1 to n do point[p[dl[i]]]:=i; fillchar(yes,sizeof(yes),false); for i:=1 to n do if not yes[i] then begin l:=0; sum:=0; temp:=maxlongint; k:=i; repeat inc(l); if p[k]<temp then temp:=p[k]; sum:=sum+p[k]; yes[k]:=true; k:=point[p[k]]; until yes[k]; if sum+temp*(l-2)<sum+temp+(l+1)*min then ans:=ans+sum+temp*(l-2) else ans:=ans+sum+temp+(l+1)*min; end; writeln(ans); end.