POJ 610. 纪念品分组
原题链接
简单
作者:
cocoonnnp
,
2022-03-29 15:52:50
,
所有人可见
,
阅读 122
简单贪心
//贪心:先排序 从大到小枚举n次 每次装最大的两个 装不了两个的就单独分组
#include <iostream>
#include <algorithm>
using namespace std;
const int N=30010;
int a[N],b[N];
int res=0;
int main(){
int w,n;
cin>>w>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n,greater<int>());
for(int i=0;i<n;i++)
{
if(b[i]==0)
{
for(int j=i+1;j<n;j++)
{
if(b[j]==0 && a[i]+a[j]<=w)
{
//cout<<a[i]<<' '<<a[j]<<endl;
b[i]=1,b[j]=1;
res++;
break;
}
}
}
}
for(int i=0;i<n;i++)
{
if(b[i]==0)
{
//cout<<a[i]<<endl;
res++;
}
}
cout<<res;
return 0;
}