题解 纪念品分组

发表于 分类于 阅读次数： 本文字数： 590

快要 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;
}

证明

可以参考这个

结语

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