旅游后台网站,如何增加网站关键词,怎样做网站导购,深圳互联网推广公司排名[NOIP2007 普及组] 纪念品分组
题目描述
元旦快到了#xff0c;校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡#xff0c;他要把购来的纪念品根据价格进行分组#xff0c;但每组最多只能包括两件纪念品#xff0c; 并且…[NOIP2007 普及组] 纪念品分组
题目描述
元旦快到了校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡他要把购来的纪念品根据价格进行分组但每组最多只能包括两件纪念品 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品乐乐希望分组的数目最少。
你的任务是写一个程序找出所有分组方案中分组数最少的一种输出最少的分组数目。
输入格式
共 n 2 n2 n2 行
第一行包括一个整数 w w w为每组纪念品价格之和的上限。
第二行为一个整数 n n n表示购来的纪念品的总件数 G G G。
第 3 ∼ n 2 3\sim n2 3∼n2 行每行包含一个正整数 P i P_i Pi 表示所对应纪念品的价格。
输出格式
一个整数即最少的分组数目。
样例 #1
样例输入 #1
100
9
90
20
20
30
50
60
70
80
90样例输出 #1
6提示 50 % 50\% 50% 的数据满足 1 ≤ n ≤ 15 1\le n\le15 1≤n≤15。 100 % 100\% 100% 的数据满足 1 ≤ n ≤ 3 × 1 0 4 1\le n\le3\times10^4 1≤n≤3×104 80 ≤ w ≤ 200 80\le w\le200 80≤w≤200 5 ≤ P i ≤ w 5 \le P_i \le w 5≤Pi≤w。 每天最惬意的就是听歌喝茶切水题普及题小小的也很可爱 #includebits/stdc.h
using namespace std;
int n,m;
int a[30004];
int main()
{cinm;cinn;int ans0;for(int i1;in;i)cina[i];sort(a1,a1n);for(int i1,jn;ij;j--){if(a[i]a[j]m)ans;else if(a[i]a[j]m)ans,i;}coutansendl;return 0;
}
