毛豆

用户名：liuyt

访问量：16848

签　名：

等　　级
排　　名	1025
经　　验	3310
参赛次数	3
文章发表	34
年　　龄	22
在职情况	学生
学　　校	燕山大学
专　　业	计算机

　　自我简介：

TA的其他文章

肺炎大作战-题解(C++代码)
浏览：186

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

纪念品的分组

　　作者: 毛豆　　　　发表时间：2019-09-13 20:21:19 浏览：333　|　评论：0　

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。 
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

【输入】 
输入文件group.in包含n+2行： 
第1行包括一个整数w，为每组纪念品价格之和的上限。 
第2行为一个整数n，表示购来的纪念品的总件数。 
第3～n+2行每行包含一个正整数pi(5<=pi<=w)，表示所对应纪念品的价格。

【输出】 
输出文件group.out仅一行，包含一个整数，即最少的分组数目。

【输入输出样例】 
group.in group.out 
100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90 6

【限制】 
50％的数据满足：l<=n<=15 
100％的数据满足：1<=n<=30000，80<=w<=200

首先分析一下大致思路
贪心法，先排序，然后按以下贪心策略： 
设s为所需的组数。i,j为两个指针，开始时指向头和尾。 
1． 如果a[i]+a[j]<=w，s=:s+1，i:=i+1，j:=j-1。 
2． 如果a[i]+a[j]>w，s:=s+1，j:=j-1。 
因为n<=300000,所以用选择排序可能会超时，最好用快速排序。

a2_1(input,output); 
    var 
    a:array[1..30000] of integer; 
    w,n,i,j,s:integer; 
    procedure qsort(h,t:integer); 
    var 
    p,i,j:integer; 
    begin 
    i:=h; 
    j:=t; 
    p:=a[i]; 
    repeat 
    while (a[j]>p) and (j>i) do j:=j-1; 
    if j>i then 
    begin 
    a[i]:=a[j]; 
    i:=i+1; 
    while (a[i]<p) and (i<j) do i:=i+1; 
    if i<j then 
    begin 
    a[j]:=a[i]; 
    j:=j-1; 
    end; 
    end; 
    until i=j; 
    a[i]:=p; 
    i:=i+1; 
    j:=j-1; 
    if i<t then qsort(i,t); 
    if j>h then qsort(h,j); 
    end; 
    begin 
    assign(input,'group.in'); 
    assign(output,'group.out'); 
    reset(input); 
    rewrite(output); 
    readln(w); 
    readln(n); 
    for i:=1 to n do readln(a[i]); 
    qsort(1,n); {快速排序} 
    i:=1; 
    j:=n; 
    s:=0; 
    while i<=j do {贪心法} 
    begin 
    if i=j then 
    begin 
    s:=s+1; 
    break; 
    end; 
    if a[i]+a[j]<=w then 
    begin 
    i:=i+1; 
    j:=j-1; 
    s:=s+1; 
    end; 
    if a[i]+a[j]>w then 
    begin 
    s:=s+1; 
    j:=j-1; 
    end; 
    end; 
    writeln(s); 
    close(input); 
    close(output); 
    end. 
    
	【深入思考】 
快速排序的程序比较难编，是否能有一种比较好编得排序方法呢？答案是肯定的。设p数组的下标为5至200，每读入一个数字x，就将p[x]加1，这样数字全部读入后就是有序的了，效率甚至比快速排序还高。这样的话贪心部分也要有所改变。

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言训练-亲密数（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

回文数字（C++代码）

纪念品的分组

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

1124题解

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

The 3n + 1 problem （C语言代码）

大神老白（C语言代码）

杨辉三角（C语言代码）

小O的数字（C语言代码）

1063题初学者，求帮忙看下,不知道哪错了

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言训练-亲密数 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

回文数字 （C++代码）

纪念品的分组

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

1124题解

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

The 3n + 1 problem （C语言代码）

大神老白 （C语言代码）

杨辉三角 （C语言代码）

小O的数字 （C语言代码）

1063题 初学者，求帮忙看下,不知道哪错了

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言训练-亲密数（C语言代码）

回文数字（C++代码）

　　评论区

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

大神老白（C语言代码）

杨辉三角（C语言代码）

小O的数字（C语言代码）

1063题初学者，求帮忙看下,不知道哪错了