NOIP2007 普及组 纪念品分组

第一个方法很容易想到，先将n个数从小到大排序，在后面比较大的数选择一个数+最小的数要<=k,当然要满足贪心的要求，足够的接近k，找到了就删除最小的数和这个数，再继续一样的操作，没有找到就可以直接判断结果了，因为剩下的数都是一个数一组的，但是找数可不能直接一个循环查找，n比较大，时间复杂度n^2肯定超时，除非数据不行，所以一般要线性时间或者nlogn才可以，所以使用二分查找logn时间复杂度，但是还要删除数啊，普通数组删除数比较麻烦，所以使用STL的vector，比较方便。

赋代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>G;
int n,k;
void match(int Min)
{
    int r=0;int l=G.size()-1;while(r<l){
    int tmp=(r+l)>>1;if(G[tmp]>Min){
    if(l!=tmp)l=tmp;	elsebreak;}else{
    if(r!=tmp)r=tmp;elsebreak;}}if(r<l) for(int i=l;i>=r;i--){
    if(Min>=G[i]){
    G.erase(G.begin()+i);return ;}}else{
    G.erase(G.begin()+r);}
} 
int main()
{
    scanf("%d%d",&k,&n);for(int i=0;i<n;i++){
    int m;scanf("%d",&m);G.insert(G.begin()+G.size(),m);}sort(G.begin(),G.end());int cnt=0;bool isok=true;while(isok){
    int Min = *G.begin();G.erase(G.begin());if(G.size()==0){
    cnt++;break;}if(Min + *G.begin()>k){
    cnt++;cnt+=G.size();break;}match(k-Min);cnt++;}printf("%d\n",cnt);return 0;
}

第二个方法，首先以为都是一个数一组，组数=n，再判断最大的数是否可以和最小的的数一个组，不可以就说明，最大的数肯定是单独一个组的，删除最大的数，组数不变，如果可以就删除最大的数和最小的数，组数-1，因为最大的数的组可以删除了。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,k;
int ans[31000];
int main()
{
    scanf("%d%d",&k,&n);for(int i=0;i<n;i++)scanf("%d",&ans[i]);sort(ans,ans+n);int cnt=n,r=0,l=n-1;while(r<l){
    if(ans[r]+ans[l]<=k){
    cnt--;r++;l--;}else l--;}printf("%d",cnt);return 0;
}