题目大意:给一个最大值m,再输入n表示有n个数据后输入n个值,问数据要分组,最多两个一组并且两个值的和不能大于m,问最少分几组
思路:贪心,因为题目数据说了输入的值只可能是200以内的,那就直接建一个a[201]的数组,记录值出现的次数。最后再贪心利用值相加小于m并且对应的次数进行减少,减完之后还有剩于的次数直接在答案中加起来即可
代码如下:
#include

using namespace std;
int a[210]={0};
int main()
{
int w,n,i;
cin>>w>>n;
for(i=0;i<n;i++){
int b;
cin>>b;
a[b]++;//记录值出现次数
}
int ans=0;
for(i=0;i<205;i++){//开始分组
for(int k=200;k>=0;k--){
while((i+k)<=w&&a[i]>0&&a[k]>0){//若两者值的和小于等于m并且都还未分组的话就进行分组
a[i]--;
a[k]--;
ans++;
}
}
}
for(i=0;i<205;i++){//分组完了还有剩了说明是一个值一组的了
if(i<=w&&a[i]>0)ans+=a[i];
}
cout<<ans;
return 0;
}