ac1125.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1125;
const
  maxn=100;
var
  a:array[1..maxn]of longint;
  p:array[1..maxn]of byte;
  n,i,j:byte;
  s,m:longint;
function min(a,b:longint):longint;
  begin
    if a<b then min:=a else min:=b;
  end;
procedure go(x:byte);
  var
    c,t,y:longint;
  begin
    c:=0;t:=maxlongint;
    repeat
      inc(c);
      if a[x]<t then t:=a[x];
      y:=p[x];p[x]:=0;x:=y;
    until p[x]=0;
    inc(s,min((c-2)*t,t+(c+1)*m));
  end;
begin
  repeat
    read(n);
    if n=0 then halt;
    s:=0;m:=maxlongint;
    for i:=1 to n do begin
      read(a[i]);
      inc(s,a[i]);
      if a[i]<m then m:=a[i];
    end;
    fillchar(p,sizeof(p),1);
    for i:=2 to n do
      for j:=1 to i-1 do
        if a[i]>a[j] then inc(p[i]) else inc(p[j]);

    for i:=1 to n do
      if p[i]>0 then
        go(i);
    writeln(s);
  until false;
end.