紀念品分組 2007年NOIP全國聯賽普及組，2007年noip
題目描述
元旦快到了，校學生會讓樂樂負責新年晚會的紀念品發放工作。為使得參加晚會的同學所獲得的紀念品價值相對均衡，他要把購來的紀念品根據價格進行分組，但每組最多只能包括兩件紀念品，並且每組紀念品的價格之和不能超過一個給定的整數。為了保證在盡量短的時間內發完所有紀念品，樂樂希望分組的數目最少。
你的任務是寫一個程序，找出所有分組方案中分組數最少的一種，輸出最少的分組數目。
輸入輸出格式
輸入描述：
包含n+2行：
第1行包括一個整數w，為每組紀念品價格之和的上限。
第2行為一個整數n，表示購來的紀念品的總件數。
第3~n+2行每行包含一個正整數pi (5 <= pi <= w)，表示所對應紀念品的價格。
輸出描述：
僅一行，包含一個整數，即最少的分組數目。
輸入輸出樣例
輸入樣例#1：
100
9
90
20
20
30
50
60
70
80
90
輸出樣例#1：
6
思路
先將數據快排，然後for循環將第一個與最後一個相加，如果得數不大於紀念品價格之和的上限，第一個與最後一個為一組。否則，將第二個與最後一個匹配，以此類推。
代碼
![]()
#include<stdio.h>
long long a[30010];
void qsort(int l,int r)
{
int i,j,mid,p;
i=l;j=r;
mid=a[(l+r)/2];
do
{
while(a[i]<mid)
i++;
while(a[j]>mid)
j--;
if(i<=j)
{
p=a[i];
a[i]=a[j];
a[j]=p;
i++;j--;
}
}while(i<=j);
if(l<j)
qsort(l,j);
if(i<r)
qsort(i,r);
}
int main()
{
long long n,i,w,k=0,j,l;
scanf("%lld%lld",&w,&n);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
qsort(1,n);
l=1;
for(i=n;i>=l;i--)
{
if(a[i]+a[l]<=w)
l++;
k++;
}
printf("\n%lld",k);
return 0;
}
View Code
