首页 > 代码库 > uva 1149:Bin Packing(贪心)
uva 1149:Bin Packing(贪心)
题意：给定N物品的重量，背包容量M，一个背包最多放两个东西。问至少多少个背包。
思路：贪心，最大的和最小的放。如果这样都不行，那最大的一定孤独终生。否则，相伴而行。
代码:
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 100100int a[N];int main() { int t; scanf("%d", &t); bool isfirst = true; while (t--) { if (isfirst) isfirst = false; else puts(""); int n; scanf("%d", &n); int l; scanf("%d", &l); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } sort(a,a+n); int st = 0; int ed = n-1; int cnt = 0; while (st <= ed) { if (st != ed){ if (a[st]+a[ed] <= l) { st++; ed--; cnt++; } else { ed--; cnt++; } } else { cnt++; ed--; } } printf("%d\n", cnt); } return 0;}
uva 1149:Bin Packing(贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。