你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。输入格式 输入包含n+2行:
第1行包括一个整数w,为每组纪念品价格之和的上限。
第2行为一个整数n,表示购来的纪念品的总件数。
第3~n+2行每行包含一个正整数pi (5 <= pi <= w),表示所对应纪念品的价格。输出格式 输出仅一行,包含一个整数,即最少的分组数目。样例输入100
9
90
20
20
30
50
60
70
80
90样例输出6数据规模和约定 50%的数据满足:1 <= n <= 15
100%的数据满足:1 <= n <= 30000, 80 <= w <= 200 示例代码:
1 #include <iostream>
2 #include <algorithm>
3 #include <cstdio>
4 using namespace std;
5
6 int main()
7 {
8 int w, n;
9 scanf("%d %d", &w, &n);
10
11 int * p = new int[n];
12
13 for (int i = 0; i < n; i++)
14 {
15 scanf("%d", &p[i]);
16 }
17
18 sort(p, p+n);
19
20 int cnt = 0; //分组数
21 for (int i = 0, j = n-1; i <= j; j--) //i指向第一件物品,j指向最后一件物品
22 {
23 if (p[i] + p[j] <= w) //如果第i件物品和第j件物品之和不超过上限,分组数加1,且判断i+1和j-1物品是否可以组合
24 {
25 i++;
26 }
27 cnt++; //如果第i件物品和第j件物品之和超过上限,那么第j件物品独立为一组,j变为j-1继续与i物品判断是否可以组合
28 }
29 printf("%d", cnt);
30
31 return 0;
32 }