洛谷1094纪念品分组题目题解代码

93 阅读 0 评论 62 点赞

我是靠谱客的博主激昂金毛，这篇文章主要介绍洛谷1094纪念品分组题目题解代码，现在分享给大家，希望可以做个参考。

题目

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

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

题解

复制代码

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

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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.