思路:
每一组最多两个礼品,贪心。
1.如果枚举最小的礼品,要去找是否有礼品和它组队,而且枚举下一个礼品时还要判断是否组队了,比较麻烦。
2.如果枚举最大的礼品,升序排序,如果最前面的礼品可以和这个礼品放一组,那么去掉这两个礼品,继续枚举下一个礼品。
3.比较简单,代码会好懂些。
Code:
#include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; int a[30005],ans; int main() { js; int w,n; cin>>w>>n; for(int i=1;i<=n;++i) cin>>a[i]; sort(a+1,a+1+n); for(int i=1,j=n;j>=i;--j) { if(a[j]+a[i]<=w) ++i; ++ans; } cout<<ans<<endl; return 0; }
一组数据
输入:
100
3
20 20 60
输出:
2
我的第一个代码输出1都ac了,有点水,因为数据水ac的代码 传送门。