思路
- 排序,贪心:找一个最大的和最小的放在一组
- 两个指针,一个在开头,一个在结尾
- 如果加起来小于上限,则记录一组答案
- 最后没有被放入的要单独处理,即独自一个组
参考代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 30010;
int a[N];
bool flag[N];
int n,w;
int main()
{
cin>>w>>n;
int ans=0;
for(int i=0;i<n;++i)cin>>a[i];
sort(a,a+n);
for(int i=0,j=n-1;i<j;){
if(a[i]+a[j]<=w){
ans++;
flag[i]=flag[j]=true;
i++;
j--;
}
else{
j--;
}
}
for(int i=0;i<n;++i)if(!flag[i])ans++;
cout<<ans<<endl;
return 0;
}