合并果子解题报告.doc

合并果子解题报告1. 首先的思路是先排序，然后找到两个最小的，插入排序到原来的序列中，速度很慢var a:array0.10000 of longint; n,total:longint; i:integer;procedure swap(var a,b:longint);var t:integer;begint:=a; a:=b; b:=tend;procedure quick_sort(m,n:integer);var i,j,x:integer;begini:=m; j:=n; x:=a(i+j) div 2;repeat while aix do inc(i); while xaj do dec(j); if ij;if mj then quick_sort(m,j);if in then quick_sort(i,n);end;procedure insert_sort(n:integer);var i,j:integer;begini:=n-1; a0:=an;while aia0 do begin ai+1:=ai; dec(i)end;ai+1:=a0end;beginreadln(n);for i:=1 to n do read(ai);quick_sort(1,n);for i:=1 to n-1 do begin an-i:=an-i+an-i+1; an-i+1:=0; inc(total,an-i); insert_sort(n-i)end;writeln(total);end.2. 我们可以通过堆排序找最小值var a:array0.20000 of longint;i,j,n,ed,sum,t:longint;procedure heapdown(i,n:longint);var j,t:longint;beginj:=i*2;while j=n do begin if (jn) and (aj+1aj then begin t:=ai; ai:=aj; aj:=t; i:=j; j:=i*2; end else j:=maxlongint; end;end;beginreadln(n);for i:=1 to n do read(ai);for i:=n div 2 downto 1 do heapdown(i,n);sum:=0;while n1 do begin t:=an;an:=a1;a1:=t; heapdown(1,n-1); dec(n); t:=an;an:=a1;a1:=t; heapdown(1,n-1); an:=an+an+1; sum:=sum+an; end;writeln(sum);end.3. 我们可以通过维护两个单调队列来完成vartot:array0.20000 of longint;quea,queb:array0.10000 of longint;i,j,n,la,lb,ra,rb,x,max,k,a1,a2,b1,b2,sum:longint;procedure minx;var i,j:longint;begin if (a1b1) and (a2b1) then begin inc(la,2); inc(rb,1); quebrb:=a1+a2; dec(k); sum:=sum+a1+a2; exit; end; if (b1a1) and (b2max then max:=x; end;la:=1;lb:=1;ra:=0;rb:=0;for i:=1 to max do for j:=1 to toti do begin inc(ra); queara:=i; end;k:=n;while k1 do begin a1:=0;a2:=0;b1:=0;b2:=0; if la=ra then a1:=queala else a1:=maxlongint; if la+1=ra then a2:=queala+1 else a2:=maxlongint; if lb=rb then b1:=queblb else b1