时间限制：1.0s 内存限制：256.0MB
关键字：贪心 排序
问题描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值 相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时 间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入格式
输入包含n+2行：
第1行包括一个整数w，为每组纪念品价格之和的上限。
第2行为一个整数n，表示购来的纪念品的总件数。
第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。
输出格式
输出仅一行，包含一个整数，即最少的分组数目。
样例输入
100
9
90
20
20
30
50
60
70
80
90
样例输出
6
数据规模和约定
50%的数据满足：1 <= n <= 15
100%的数据满足：1 <= n <= 30000, 80 <= w <= 200
【分析】
由于题目要求每组纪念品价格之和的上限，并且每组最多只能包括两件纪念品，由此可以知道如果某件纪念品价格大于价格上限减去最小值，则需要独立一组，等于上限与最小值的差值的价格可以和最小值分在同一组，剩余的任意组合成两组即可满足条件。
【参考代码】
C++：
#include "iostream"
#include "string"
#include "stdio.h"
#include "ctype.h"
#include "algorithm"
#include "stack"
#include "list"
#include "math.h"
using namespace std;
const int N =30001;
int a[N];
int main()
{
int n;
int w;
cin>>w>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
std::sort(a,a+n);
int ans=0;
for(int i=0,j=n-1;i<=j;)
{
for(;i<j;j--)
{
if(a[i]+a[j]<=w)
break;
else ans++;
}
if(i!=j)
{
i++;j--;
ans++;
}
else
{
ans++;
break;
}
}
cout<<ans;
return 0;
}
C：
#include <stdio.h>
void qsort(int i,int j);
int a[30000];
void qsort(int i,int j){
int x,p,q;
x=a[i]; p=i; q=j;
while (i<j) {
while ((i<j)&&(a[j]>x))
j--;
if (i<j)
{
a[i]=a[j];
i++;
}
while ((i<j)&&(a[i]<x))
i++;
if (i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=x;
if (p<i-1)
qsort(p,i-1);
if (i+1<q)
qsort(i+1,q);}
main(){
int n,w,s,i,j;
scanf("%d%d",&w,&n);
for (i=0;i<n;i++)
scanf("%d",&a[i]);
qsort(0,n-1);
i=0;
j=n-1;
s=0;
while (i<j)
{
s++;
if (a[i]+a[j]<=w)
{
i++;
j--;
}
else j--;
}
if ((i==j)&&(a[i]<=w))
s++;
printf("%d",s);
getchar();
getchar();
return(0);
}
Java：
import java.io.*;
import java.util.Arrays;
public class Main {
static int a[]=new int[30001];
public static void main (String args[])throws IOException{
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
int w=Integer.parseInt(bf.readLine());
int n=Integer.parseInt(bf.readLine());
for(int i=1;i<30001;i++)
a[i]=999999;
int k=n;
int sum=0;
for(int i=1;i<=n;i++)
a[i]=Integer.parseInt(bf.readLine());
Arrays.sort(a);
oter:for(int i=1;i<=n;i++){
for(int j=n;j>0;j--){
if(k==i){
sum++;
break oter;
}
if(k-i==1&&a[i]+a[k]>w){
sum+=2;
break oter;
}
if(k-i==1&&a[i]+a[k]<=w){
sum++;
break oter;
}
if(a[i]+a[k]>w){
k--;
sum++;
}
else{
sum++;
k--;
break;
}
}
}
System.out.println(sum);
}
}
上面的Java代码是参考资料里的，下面是我自己的写的，感觉思路比较简单吧，能运行出来结果
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
public class 纪念品分组
{
public static void main(String[] args)
{
Scanner sc = new Scanner (System.in);
int max = sc.nextInt(); //纪念品和的上限
int n = sc.nextInt(); //纪念品组数
int[] arr = new int[n];
for (int i=0; i<n; i++) //遍历存储纪念品的价格
{
arr[i] = sc.nextInt();
}
Arrays.sort(arr); //纪念品价格排序
int min = arr[0]; //价格最小值
int temp = max - min; //中间变量：价格上限和最小值的差值
int count = 0;
int count1 = 0;
int count2 = 0;
for (int i=0; i<n; i++)
{
if (arr[i] > temp)
{
count++; //单独一组的数量
}
if (arr[i] == min)
{
count1++; //最小值的数量
}
if (arr[i] == temp)
{
count2++; //能与最小值凑成一组刚好等于价格上限的数量
}
}
int a = Math.min(count1, count2); //价格之和等于价格上限的组数
if ((n - count - 2*a)%2 == 0) //判断剩余的是否能刚好分成两件一组
{
count = count + a + (n - count - 2*a)/2;
}
else
count = count + a + (n - count - 2*a)/2 + 1;
System.out.println(count);
}
}