題解 紀念品分組

快要 CSP-S2 了，複習一下一些演算法（弄文化課弄了好久了，很多東西都要忘了。。。

讀題

題目連結: Luogu P1094

看題，把購來的紀念品根據價格進行分組，但每組最多隻能包括兩件紀念品。看樣子，應該是貪心。每次取一個大的，一個小的，就可以保證了。如果大的小的組合起來，超過了最大值，就只取大的。

解題

很容易就可以寫出程式。

#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;
}

證明

可以參考這個

結語

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