首页 > 代码库 > Bin Packing

Bin Packing

2024-07-10 15:38:25   222人阅读

UVALive:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1504

题意：给你一个长度为L的盒子，然后有n个物品，然后给出每个物品的长度，把物品装入盒子中，但是每个盒子最多只能装两个，并且物品的长度之和要不超过盒子的长度。问你最少需要多少个盒子。

题解：直接贪心，每次选择一个最大的物品装入，然后再选择一个最小的。如果最最小的可以装下，则就装下，否则放到另外一个盒子里面。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using  namespace std; 8 int a[100002]; 9 int main(){10    int cas,temp,n,counts,L,tt=1;11    scanf("%d",&cas);12    while(cas--){13     if(tt>1)printf("\n");14          tt=2;15       scanf("%d%d",&n,&L);16       for(int i=1;i<=n;i++)17         scanf("%d",&a[i]);18         sort(a+1,a+n+1);19        int l=1,r=n,counts=0;20       while(l<=r){21         if(a[r]+a[l]<=L){22             r--;l++;23         }24          else{25             r--;26          }27          counts++;28       }29       printf("%d\n",counts);30    }31 }
View Code

 


联系
我们