当前位置: 代码迷 >> 综合 >> 紫书 习题 8-1 UVa 1149(贪心)
  详细解决方案

紫书 习题 8-1 UVa 1149(贪心)

热度:112   发布时间:2023-09-20 22:05:17.0

排序之后, 尽量最小和最大的放在一个背包, 放不下就放最大的。

#include<cstdio>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112345;
int a[MAXN];int main()
{int n, lmax;int T, kase = 0;scanf("%d", &T);while(T--){if(kase) puts(""); kase = 1;	scanf("%d%d", &n, &lmax);REP(i, 0, n) scanf("%d", &a[i]);sort(a, a + n);int ans = 0;int l = 0, r = n - 1;while(l <= r){ans++;if(a[l] + a[r] <= lmax) l++, r--;else r--;}printf("%d\n", ans);}return 0;
}