箱子打包 贪心算法

题目来源：https://acm.ecnu.edu.cn/problem/1045

//B站网盘 箱子打包

//思路：每次只装一个箱子，选最大和最小的装箱，若溢出则只装最大的物品
//尽可能少的装箱数 贪心策略
// 1、将问题拆分 考虑每次只装一个箱子
//2、保证该箱子尽可能装的满（不能超过两个物品） 如果排序后，只装最小两个值 两个值 会浪费空间
        //每次选最大的和最小的商品装箱 若溢出，则只装最大的商品，因为我们对商品拍虚了
        //如果小商品A和大商品D没办法，还要装A，则之后的B会更大，会更装不下，于是选最小的和最大的，溢出装最大
//3、局部->全局

#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1e5 +10;
int length[MAXN];//有n个物品，每次输入它的长度
int main()
{
    int n,l;//n是物品的长度 l是箱子的固定长度
   scanf("%d%d",&n,&l);

        //scanf("%d",&l);//输入箱子的长度
        for(int i=0;i<n;i++)
        {
            scanf("%d",&length[i]);
        }//输入n个物品的长度
        //对装入物品的长度排序
        sort(length,length+n);//升序排
        int left=0;
        int right=n-1;
        int q=0;//箱子总数
        //贪心算法拆解 装一个箱子。选择最小和最大，如果溢出，则装入最大
        while(left<=right)
        {
//            if(left==right)
//                {
//                    q++;
//                    break;
//                }//这段判断是考虑到了只有最后一个物品的情况，但是当只有最后一个物品的时候
//              left ==right 同样满足以下的ifelse 如果相加<l q++ 如果大于l 只装入一个 right-- 此时left!=right 可以跳出循环
            if(length[left]+length[right]<=l)
            {
               // q++;//如果可以装入则q++
                left++;
                right--;
            }
            else//如果选择的最大值和最小值装不下这个箱子，装入最大值物品
            {
                //q++;
                right--;
            }
            q++;

        }

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

    return 0;
}