将序列排序
找出所有的循环，即错误位置调换的循环 如 2 4 1 3 循环为 2->4->3->1->2 Ans=sigma 循环长度-1 参考程序： var
a,b:array[0..1000000]of longint; n,i,j,tot,t,ans:longint;
use:array[0..1000000]of boolean;
procedure qsort(l,r:longint); var
i,j,x,t:longint; begin
i:=l; j:=r; x:=a[random(r-l+1)+l]; repeat
while a[i]
t:=a[i]; a[i]:=a[j]; a[j]:=t; t:=b[i]; b[i]:=b[j]; b[j]:=t; inc(i); dec(j); end; until i>j;
if i begin assign(input,'seqsort.in'); reset(input); readln(n); for i:=1 to n do begin read(a[i]); b[i]:=i; end; close(input); qsort(1,n); for i:=1 to n do a[i]:=i; for i:=1 to n do if not use[i] then begin t:=i; tot:=0; while not use[t] do begin use[t]:=true; inc(tot); t:=b[t]; end; ans:=ans+tot-1; end; assign(output,'seqsort.out'); rewrite(output); writeln(ans); close(output); end. 输入 15 18 25 -30 76 125 67 45 -72 186 100 29 14 88 77 127 输出 13 输入 24 25 18 30 60 200 -104 -32 90 88 64 187 45 36 62 78 94 13 33 24 -56 82 140 189 71 输出 18 【问题描述】 Matrix67要在下个月交给老师n篇论文，论文的内容可以从m个课题中选择。由于课题数有限，Matrix67不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题i，若Matrix67计划一共写x篇论文，则完成该课题的论文总共需要花费Ai*x^Bi个单位时间（系数Ai和指数Bi均为正整数）。给定与每一个课题相对应的Ai和Bi的值，请帮助Matrix67计算出如何选择论文的课题使得他可以花费最少的时间完成这n篇论文。 【输入文件】 第一行有两个用空格隔开的正整数n和m，分别代表需要完成的论文数和可供选择的课题数。 以下m行每行有两个用空格隔开的正整数。其中，第i行的两个数分别代表与第i个课题相对应的时间系数Ai和指数Bi。 【输出文件】 输出完成n篇论文所需要耗费的最少时间。 【样例输入】 10 3 2 1 1 2 2 1 【样例输出】 19 【样例说明】 4篇论文选择课题一，5篇论文选择课题三，剩下一篇论文选择课题二，总耗时为2*4^1+1*1^2+2*5^1=8+1+10=19。可以证明，不存在更优的方案使耗时小于19。 【数据规模与约定】 对于30%的数据，n<=10,m<=5； 对于100%的数据，n<=200，m<=20，Ai<=100，Bi<=5。 var a,b,i,j,k,n,m:integer; c:array[1..20,1..200] of int64; {预处理数组} f:array[0..200] of int64; begin assign(input,'mat.in'); assign(output,'mat.out'); reset(input); rewrite(output); readln(n,m); for k:=1 to m do begin readln(a,b); for i:=1 to n do begin c[k,i]:=a; for j:=1 to b do c[k,i]:=c[k,i]*i; end; end; f[0]:=0; for i:=1 to n do f[i]:=100000000000000000; for k:=1 to m do for i:=n-1 downto 0 do for j:=1 to n-i do if f[i]+c[k,j] 输入20 5 2 1 1 2 2 1 2 1 1 2 输出 38 输入 16 7 2 3 3 1 3 2 2 1 2 3 3 2 1 3 输出 31