纪念品分组

解题过程

1.获取价格总和上限w，纪念品总件数n
2.循环n次，依次获取纪念品价格，存入数组a[]
3.对数组a从低到高排序
4.贪心算法：定义两个指针i,j（两个int型变量，用来表示数组的下标），i=0，j=n-1
两个指针一起向中间走，每次选择都尽可能的让当前状态下最大值和最小值分在一组，如果不行就让最大值单独分一组，这样分组数才能最少
5.输出分组数

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int w,n;//价格总和上限w，纪念品总件数n
    cin>>w>>n;
    int a[30000];//存放纪念品价格
    int i=0;//数组首元素下标
    int j=n-1;//数组末元素下标
    int count=0;//组数
    //获取每件纪念品价格
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }

    //排序
    sort(a,a+n);
    //贪心算法
    while(i<=j)
    {
        if (a[i]+a[j]<=w)//将a[i]和a[j]归为一组
        {
            count++;
            i++;
            j--;
        }
        else//将a[j]单独当作一组
        {
            count++;
            j--;
        }
    }
    //输出组数
    cout<<count<<endl;
    return 0;
}