企业网站建设大概需要多少钱,鹤壁做网站推广,游戏怎么制作,网站营销目标刚刚做出这道题#xff0c;感觉很兴奋啊#xff0c;对于我这种弱菜来说能完美的AC这道题真是令人振奋不已啊#xff01; #xff08;情不自禁的将AC记录发上来了#xff0c;勿怪勿怪#xff01;#xff09; 这道题是我们向总点名要做的#xff0c;这几天学了很多新内容… 刚刚做出这道题感觉很兴奋啊对于我这种弱菜来说能完美的AC这道题真是令人振奋不已啊 情不自禁的将AC记录发上来了勿怪勿怪 这道题是我们向总点名要做的这几天学了很多新内容于是乎拖到了今天才做。 由于刚刚学了堆排序仔细一看这道题的描述感觉用堆排序来做真是再合适不过了网上貌似有很多做法快排什么有机会换个算法编一下因为只需要将合并产生的数据放入堆中筛一遍即可。 刚开始认为只不过是简单的将堆排序中将第一个置换为最后一个并将dec(记录指针2)就可以了。就这样随便整了一下就交上去了发现只有10分说到这个10分某位大神还以为是哪个小地方出了问题结果我一看测试数据发现对的那个点就是题目给出的例子蛋疼有木有。 冥思苦想了好一会终于想明白了不要一次性将第一第二两个值全换掉这样堆筛下来无法得到正确的序列。先将最后一个置换为第一个筛一遍由于筛过后排在第一个的数据一定是刚刚第二小的数据只需要用刚刚记录下来的x[1]x[2]将其置换即可。 务必记在在dec(指针之前将当前指向的数据赋值为maxlongint否则会造成严重后果就是被这个卡了好久因为数组很大之后的数据全部为0会造成将0置换上来的情况置为maxlongint便不会出现这个问题。 废话不多说直接上源代码 1 program duipaixu2;2 type3 arrarray[1..10001] of longint;4 var5 x:arr;6 i,j,j1,n:longint;7 bool:boolean;8 s,s1:int64;9 procedure heap(var x:arr;j,i:longint);【堆排序】
10 var
11 i2,t1:longint;
12 begin
13 t1:x[i];
14 i2:2*i;
15 while i2j do
16 begin
17 if (i2j) and (x[i2] x[i21]) then i2:i21;
18 if t1 x[i2] then
19 begin
20 x[i]:x[i2];
21 i:i2;i2:2*i;
22 end
23 else i2:j1;
24 end;
25 x[i]:t1;
26 end;
27 { main }
28 begin
29 assign(input,hebin.in);
30 assign(output,hebin.out);
31 reset(input);
32 rewrite(output);
33 read(n);
34 for i:1 to n do
35 read(x[i]);
36 x[n1]:maxlongint;
37 j:n;
38 s:0;
39 s1:0;
40 for i:n div 2 downto 1 do 【建立新堆】
41 heap(x,n,i);
42 repeat
43 bool:true;
44 if x[2]x[3] then
45 begin
46 s1:x[1]x[2];
47 s:ss1;
48 end
49 else begin s1:x[1]x[3];s:ss1 end;
50 j1:j;
51 dec(j);
52 if j1 then
53 begin
54 x[1]:x[j1];
55 x[j1]:maxlongint; 【这一步很重要否则会出现上文提到的结果】
56 heap(x,j,1); 【分两次筛】
57 x[1]:s1;
58 heap(x,j,1);
59 end;
60 until j1;
61 write(s);
62 close(input);
63 close(output);
64 end.By ZYT12.10.05 转载于:https://www.cnblogs.com/cszyt/archive/2012/10/05/2712452.html
