不是VIP会员,不能显示答案

题目解答

题目:
买书
书店有个买2送1的活动:买3本书只要付较贵的2本就可以了。举个例子:
10 3 2 4 6 4 9 , 如果这样组合(10, 3, 2), (4, 6, 4) and(9),就能在第一个括号中省下2元,第二括号中省下4元,但第三个括号不能省了,因为不足3本书。
售货员是个热心肠也爱动脑筋的人,他想为每位顾客尽可能多的省钱,请你帮助她吧。
注意:不一定非要组合三本书一堆,但一堆的数量必须是1到3
输入的第一行一个整数N,表示书的数量。接下来的N行,每行包含一个整数Ci,表示每本书的价格。输出一个数。表示最终要为这些书付出的最小价格。
解题思路:贪心的策略,按照书费的降序排序,挑尽可能贵的2本放在一起来省去书费,反复操作,直到书少于3本样例中10 3 2 4 6 4 9 就可以这样分组:
(10 9 6) 、(4 4 3)、(2),很显然省去了6+3+2=9,这是最省钱的分组方案,根据这个思路,请完善以下程序
var
n,i:longint;
a:array[0..100001] of longint; 
s:int64;
procedure sort(l,r:longint);//sort过程实现a数组值的降序排序
var i,j,x,y:longint;
begin
i:=l; j:=r; x:=a[(l+r) div 2]; 
repeat
while x<a[i] do inc(i); 
while x>a[j] do dec(j); 
if not(i>j) then 
begin
y:=a[i];a[i]:=a[j]; a[j]:=y; 
inc(i); j:=j-1;
end;
until i>j; 
if l<j  then sort(l,j); 
if i<r then sort(i,r); 
end; 
begin 
readln(n); 
for i:= 1 to n do 
read(a[i]); 
sort(1,n); 
for i:= 1 to n do 
if i mod 3<>0 then 
s:= s+a[i]; 
writeln(s); 
end.
考点:
分析:
解答:
评论:
老师: