题目

为使纪念品价值相对均衡，乐乐把纪念品根据价格进行分组，每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

题解

用快排给数据排序，然后每组选剩余纪念品中价值最大的一个和最小的一个，如果此时超出最大值，则只选最大的，重复此操作直至分完所有纪念品。

代码

var
n,w,i,j,k:longint;
a:array[1..30000]of longint;
procedure qsort(l,r:longint);
var
i,j,key,t:longint;
begin
if l>=r then exit;
i:=l;j:=r;
key:=a[l+random(r-l+1)];
repeat
while a[i]<key do inc(i);
while a[j]>key do dec(j);
if i<=j then
begin
t:=a[i];a[i]:=a[j];a[j]:=t;
inc(i);dec(j);
end;
until i>j;
qsort(i,r);
qsort(l,j);
end;
begin
readln(w);
readln(n);
for i:=1 to n do
readln(a[i]);
randomize;
qsort(1,n);
i:=1;j:=n;
while i<=j do
begin
inc(k);
if a[i]+a[j]<=w then begin inc(i);dec(j);end else
dec(j);
end;
writeln(k);
end.

最后

以上就是激昂金毛为你收集整理的洛谷1094纪念品分组题目题解代码的全部内容，希望文章能够帮你解决洛谷1094纪念品分组题目题解代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。