题解|#箱子打包#（简单贪心）

题目

有一组 1 维的物品需要打包进一批同样的箱子中。所有的箱子有完全一样的长度 l 以及每一个物品长度 li<=l. 我们要找到一个最小的数字 q, 使得 :

(1) 每个箱子最多包含两个物品

(2) 每个物品要被包含在 q 个箱子中的一个中

(3) 在箱子中物品的总长度不能超过 l

你的任务是，给定 n 个整数，l,l1,l2....ln, 计算最小的箱子总数 q.

输入格式

第一行包含一个数字 n(1<= n <= 10^5), 表示有几个物品。第二行包含一个整数表示了箱子的长度 l (l<=10000). 接下去的 n 行是表示了每个物品的长度。

输出格式

输出一个整数，表示能够包含所有物品的最小的箱子总数。

提示 :

The sample instance and an optimal solution is shown in the figure below. Items are numbered from 1 to 10 according to the input order.

思路

箱子尽量少——>每个箱子尽量装2个物品

极端情况就是比较最长和最短的能否放一起，若不可以，则最长的必须单独放一个箱子

如果从空间利用率尽量大的角度来看，每个箱子应该和其能一起放的下的最长箱子搭配，需要再进行查找，（方法一）

进一步可以简化为直接考虑和最短的搭配（方法二）

可以使用方法二原因：

若最长的搭配不唯一，第二长的搭配也必定不唯一，那么不会出现最长的和最短的搭配导致，第二长的只能单独放的情况，所以适当牺牲局部的空间利用率无伤大雅

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>box;
int main(){
    int n,x,l;
    scanf("%d",&n);
        scanf("%d",&l);
        for(int i=0;i<n;i++){
            scanf("%d",&x);
            box.push_back(x);
        }
    
    int sum=0;
    sort(box.begin(),box.end());//按长度排序
    while(box.size()!=0){
        int i=box.size()-1;//每次先考虑最长的
        if(i==0){//只剩最后一个
            sum++;
            break;
        }
        int k=-1;
        for(int j=0;j<i;j++){//查找和当前最长物品最优的搭配
            if(box[i]+box[j]<=l)k=j;
            else break;
        }
        if(k!=-1){
            sum++;
            box.pop_back();
            box.erase(box.begin()+k);
        }
        else{
            sum++;
            box.pop_back();
        }
    }
    printf("%d\n",sum);
    
    
    return 0;
}

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>box;
int main(){
    int n,x,l;
    scanf("%d",&n);
        scanf("%d",&l);
        for(int i=0;i<n;i++){
            scanf("%d",&x);
            box.push_back(x);
        }
    
    int sum=0;
    sort(box.begin(),box.end());//按长度排序
    while(box.size()!=0){
        int i=box.size()-1;//每次先考虑最长的
        if(i==0){//只剩最后一个
            sum++;
            break;
        }
        if(box[i]+box[0]<=l){//最长的和最短的可以放进一个箱子
            sum++;
            box.pop_back();
            box.erase(box.begin());
        }
        else{//只能将最长的单独放进一个箱子
            sum++;
            box.pop_back();
        }
    }
    printf("%d\n",sum);
    
    
    return 0;
}