礼物

题目大意

你现在有 $m$ 元钱，现在有 $n$ 中不同的物品。每种物品有一个花费 $c_i$ 和幸福值 $v_i$ ,你每次可以购买两个不同的物品，你的朋友会收下幸福度较低的一个，问你的朋友最大可以获得多少幸福度

题解思路

我们希望找到所有幸福值大于等于自己的元素中花费最少的应该是多少，这样我们可以先按照幸福值进行排序，之后我们可以用一个类似于前缀最小值的方法找到相应的花费，活着直接枚举也可以。

问题就转换为一个 $n$ 个物品， $m$ 点花费的完全背包。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    //  v_i. cost
    vector<pair<i64, i64> > arr(n + 1);
    for (int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        arr[i] = {v, u};
    }
    sort(arr.begin() + 1, arr.end(), greater<>());
    vector<pair<i64, i64> > nn;
    i64 ex = arr[1].second;
    for (int i = 2; i <= n; i++) {
        nn.emplace_back(arr[i].first, arr[i].second + ex);
        ex = min(arr[i].second, ex);
    }
    vector<i64> f(m + 1);
    for (auto [v_i , c_i]: nn) {
        for (int i = c_i; i <= m; i++) {
            f[i] = max(f[i], f[i - c_i] + v_i);
        }
    }
    cout << f[m] << endl;
}