題目描述

       元旦快到了，校學生會讓樂樂負責新年晚會的紀念品發放工作。為使得參加晚會的同學所獲得的紀念品價值相對均衡，他要把購來的紀念品根據價格進行分組，但每組最多只能包括兩件紀念品，並且每組紀念品的價格之和不能超過一個給定的整數。為了保證在儘量短的時間內發完所有紀念品，樂樂希望分組的數目最少。

你的任務是寫一個程式，找出所有分組方案中分組數最少的一種，輸出最少的分組數目。

輸入輸出格式

輸入描述：

包含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;
}