Codeforces Round #683 (Div. 2, by Meet IT)C. Knapsack(贪心+思维)

题意

给你一个上界\(W\)和一系列权值\(w_i\)，让你找到权值中任意一个或多个的和满足\((W + 1) / 2\leq sum \leq W\)

思路

从大到小贪心。

证明：

? 假设我贪到了一个这个数本身是满足\((W + 1) / 2\leq sum \leq W\)那么我可以直接输出。

? 假设所有的权值都是不满足\((W + 1) / 2\leq sum \leq W\)，那么任意两个的和都是小于\(W\)的，那么当他们加起来和大于\((W + 1) / 2\)时输出就行，否则就是\(-1\)

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
const int maxn = 2e5 + 10;
struct NODE {
    int id, val;
    NODE(){}
    NODE(int _id, int _val): id(_id), val(_val){}
    bool operator < (const NODE& x) const {
        return val > x.val;
    }
} a[maxn];
 
 
void solve() {
    int n, W;
    cin >> n >> W;
    int l = (W + 1) / 2, r = W;
    vector<int>ans;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i].val;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n);
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        if(a[i].val > r) continue;
        ans.push_back(a[i].id);
        sum += a[i].val;
        if (sum >= l && sum <= r) {
            cout << ans.size() << "\n";
            for (int i = 0; i < ans.size(); ++i) {
                if (i) cout << " ";
                cout << ans[i];
            }
            cout << endl;
            return ;
        }
    }
    cout << -1 << "\n";
}
 
signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Codeforces Round #683 (Div. 2, by Meet IT)C. Knapsack(贪心+思维)

原文：https://www.cnblogs.com/waryan/p/13984515.html