首页 > 代码库 > UVa1149 Bin Packing (贪心)

UVa1149 Bin Packing (贪心)

链接:http://vjudge.net/problem/UVA-1149

 

分析:贪心的放,先放重的,剩下的容量看能不能放进一个轻的。

 

 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4  5 const int maxn = 100000 + 5; 6  7 int a[maxn]; 8  9 int main() {10     int T;11     scanf("%d", &T);12     for (int kase = 0; kase < T; kase++) {13         if (kase) printf("\n");14         int n, l;15         scanf("%d%d", &n, &l);16         for (int i = 0; i < n; i++) scanf("%d", &a[i]);17         sort(a, a + n);18         int L = 0, R = n-1, ans = 0;19         while (L <= R) {20             if (L == R) { ans++; break; }21             if (a[L] + a[R] <= l) { ans++; L++; R--; }22             else { ans++; R--; }23         }24         printf("%d\n", ans);25     }26     return 0;27 }

 

UVa1149 Bin Packing (贪心)