[NOIP2007 普及组] 纪念品分组-Toy模板网

这篇具有很好参考价值的文章主要介绍了[NOIP2007 普及组] 纪念品分组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

[NOIP2007 普及组] 纪念品分组

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入格式

共 $n + 2$ 行：

第一行包括一个整数 $w$ ，为每组纪念品价格之和的上限。

第二行为一个整数 $n$ ，表示购来的纪念品的总件数 $G$ 。

第 $3\sim n+2$ 行每行包含一个正整数 $P_i$ 表示所对应纪念品的价格。

输出格式

一个整数，即最少的分组数目。

样例 #1

样例输入 #1

样例输出 #1

提示

$50\%$ 的数据满足： $1\le n\le15$ 。

$100\%$ 的数据满足： $1\le n\le3\times10^4$ ， $80\le w\le200$ ， $\le P_i \le w$ 。

每天最惬意的就是听歌喝茶切水题，普及题小小的也很可爱
文章来源地址https://www.toymoban.com/news/detail-632229.html

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[30004];
int main()
{
	cin>>m;
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=1,j=n;i<=j;j--)
	{
		if(a[i]+a[j]>m)ans++;
		else if(a[i]+a[j]<=m)ans++,i++;
	}
	cout<<ans<<endl;
	return 0;
}