首页 > 代码库 > UVA 1149 Bin Packing
UVA 1149 Bin Packing
贪心
对所有物品排序，然后从大头拿一个，检测如果加上此时最小的是否满足<=M，是的话就拿，不是的话就不拿
注意此题的输出要求！！！
多组样例的时候，每两组样例中要有一个空行！
而一组样例的时候，不要输出多余的空行。（因为这个WA卡住半个小时T T，最后还是去网上搜别人代码发现的，虽然以前有的题或是OJ会忽略最后一行空行，但是还是改掉这个坏习惯好）
AC代码
#include <iostream>#include <cstdio> #include <algorithm>#include <cstring>#define maxn 100000+10using namespace std;int a[maxn];int cmp(int a,int b){ return a>b;}int work(int n,int m){ int ans=0; int i=0,j=n-1; while (i<=j){ if (a[i]+a[j]<=m&&i!=j) j--; i++;ans++; } return ans;}int main(){ int t=0; int testcase; scanf("%d",&testcase); while (testcase--){ t++; int n,m; scanf("%d%d",&n,&m); memset(a,0,sizeof(a)); for (int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n,cmp); if(t!=1) printf("\n"); printf("%d\n",work(n,m)); }}
PS.自己一开始的贪想的有点复杂了，找最大的，然后再找当前能塞下去的最大的。这个思想的正确性我还不确定，但是仔细想想，根本不用这样贪。
UVA 1149 Bin Packing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。