0%

题解 纪念品分组

快要 CSP-S2 了,复习一下一些算法(弄文化课弄了好久了,很多东西都要忘了。。。

读题

题目链接: Luogu P1094

看题,把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品。看样子,应该是贪心。每次取一个大的,一个小的,就可以保证了。如果大的小的组合起来,超过了最大值,就只取大的。

解题

很容易就可以写出程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

int ar[30001];

int main() {
int n, w;
cin >> w >> n;
for (int i = 0; i < n; i++) cin >> ar[i];
sort(ar, ar + n);
int ans = 0;
int l = 0;
int r = n - 1;
while (r >= l) {
if (ar[l] + ar[r] <= w) {
l++;
r--;
ans++;
} else {
r--;
ans++;
}
}
cout << ans;
return 0;
}

证明

可以参考这个

结语

能力有限,如有疏漏,请谅解并补充,谢谢。

欢迎关注我的其它发布渠道