[NWPU2016][寒假作业][正常版第二组]U

题意，有箱子和物品，宽度一样，长度不一样，给定箱子和物品，一个箱子至多能装两个物品，一个物品只能被一个箱子装，求最少多少箱子能装所有的物品。

思路：贪心的话，很容易想到，从大到小排，从最大的开始，往后，看哪个和它加起来小于箱子容量，有的话做标记，下次跳过它，然后这么一写妥妥超时，得优化，然后就想到，从最大的开始，然后和它配对的从最小的开始找，而不是从i+1开始找，还是超时。。。看来还有可优化的地方，想了一会，我发现犯了个很傻的错误，那就是从最小的开始找，如果它不符合，说明剩下的都肯定不符合因为它是最小的，所以没被标记的最小的不符合的话，直接break就好，因为剩下的肯定不符合。这样就节省多了。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <map>

#include <string>

#include <string.h>

#include <queue>

#include <vector>

using namespace std;

int cmp(int a,int b)

{

        if(a>b)

        return ;

        return ;

}

int num[]={};

int flag1[]={};

int main()

{

    int n,m;

    int cnt=,sum=,flag=,count=;

    scanf("%d%d",&n,&m);

    for(int i=;i<n;i++)

    {

        scanf("%d",&num[i]);

    }

    sort(num,num+n,cmp);

    for(int i=;i<n-;i++)

    {

        if(!flag1[i])

        {

        sum=num[i];

        flag1[i]=;

        count++;

        for(int j=n-;j>i;j--)

        {

         if(sum+num[j]<=m)

             {

                if(count<&&!flag1[j])

                {

                sum+=num[j];

                count++;

                flag=;

                flag1[j]=;

                cnt++;

                break;

                }

             }

             else break;

        }

        if(!flag)

        {

           cnt++;

           count=;

        }

        flag=;

        count=;

        }

        else continue;

    }

    if(!flag1[n-])

        cnt++;

    printf("%d\n",cnt);

    return ;

}