1107: 纪念品分组

解题思路:
动态数组：vector<int>p(n)

sort 对数组进行降序排序

两重遍历，只要两项加起来小于等于w，就分为一组

已分配好的纪念品置成-1（价格不会达到的数）

第一重遍历会遇到已经分配好的纪念品（-1），则跳过该次循环，继续下一轮   if(p[i]==-1) continue;

如果有纪念品始终找不到配对的，就单独成为一组 ，即定义一个flag，判断是否被配对   if(flag==1)   cnt++;

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int w,n,i,j;

    cin>>w>>n;

    vector <int> p(n);

    for(i=0;i<n;i++){

        cin>>p[i];     //输入纪念品价格

    }    

     //降序

    sort(p.begin(),p.end(),[](int a,int b){

        return a>b;

    });

    int cnt=0;   

    for(i=0;i<n;i++){   

        int flag=1;

        if(p[i]==-1) continue;  

        for(j=i+1;j<n;j++){

            if(p[i]+p[j]<=w&&p[j]!=-1){

                flag=0;

                p[j]=-1;

                cnt++;

                break;

            }

        }

        if(flag){

            cnt++;

        }

    }

    cout<<cnt;

    return 0;

}