題解 紀念品分組

發表於 分類於 閱讀次數： Waline： 文章字數： 591

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

證明

可以參考這個

結語

能力有限，如有疏漏，請諒解並補充，謝謝。