Uva1149 Bin Packing【贪心】

题目：Bin Packing

题意：给定N（N≤105）个物品的重量Li，背包的容量M，同时要求每个背包最多装两个物品。求至少要多少个背包才能装下所有的物品。

思路：排序后，当前最大的+最小的 < L 装包，否则只装最大的，这样扫一遍就可求出最少背包！

代码：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100005; int a[maxn]; int main(){ int n,t,l; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&l); for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); int cnt = 0,pos = 0; for(int i=n-1;i>=0;i--){ if(a[i] == -1) continue;//已经装过的 if(a[i] + a[pos] <= l){//俩个：最大+最小 cnt++; a[pos++] = -1;//将装过的标记 }else cnt++;//一个：最大的 } printf("%d\n",cnt); if(t) printf("\n"); } return 0; }