首页 > 代码库 > UVa 1149 装箱
UVa 1149 装箱
https://vjudge.net/problem/UVA-1149
题意：给定N个物品的重量和背包的容量，同时要求每个背包最多装两个物品。求至少需要的背包数。
思路：很简单的贪心。每次将最轻的和最重的放一个背包里，如果放不下，则只放一个最重的。
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 const int maxn = 100000 + 5; 6 7 int n, m; 8 int a[maxn]; 9 int ans;10 11 void solve()12 {13 ans = 0;14 sort(a, a + n);15 int L = 0, R = n - 1;16 while (L <= R)17 {18 if (a[L] + a[R] <= m)19 {20 ans++;21 L++;22 R--;23 }24 else25 {26 ans++;27 R--;28 }29 }30 }31 32 int main()33 {34 //freopen("D:\\txt.txt", "r", stdin);35 int t;36 cin >> t;37 while (t--)38 {39 cin >> n >> m;40 for (int i = 0; i < n; i++)41 {42 cin >> a[i];43 }44 solve();45 cout << ans << endl;46 if (t) cout << endl;47 }48 return 0;49 }
UVa 1149 装箱
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。