【贪心】代码源每日一题div2 背包

浅浅的花香味﹌ 2024-03-16 18:13 51阅读 0赞

[背包 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![c70769545d9f44458a024424ba7352fa.png][]

思路：

首先看数据范围是不能去背包的

那么自然而然的考虑贪心

正解是把数组从大到小排个序，能选就选，看最后是不是>=w/2即可

为什么是这样做呢，可以试想一下几种情况，**从最特殊的情况想起**

如果每个物品都是>w，那么就是NO，我们不去考虑这种物品

如果所有物品加起来都<w/2，那么就是NO

然后考虑中间情况，前面的一些都是加起来<w/2的，然后如果突然加了一个物品，然后sum>w了，那么这个物品就是>w/2的，那么直接选这个物品就可以了，总体积就是>w/2，否则就不选这个物品，那么又变成第一种情况，如果选一个物品之后sum>w/2，那么就是YES

因此NO的情况一定就是第一种或者情况，其他情况全是YES

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    
    int N,W;
    int w[mxn];
    
    bool cmp(int x,int y){
    	return x>y;
    }
    void solve(){
    	cin>>N>>W;
    	for(int i=1;i<=N;i++) cin>>w[i];
    	sort(w+1,w+1+N,cmp);
    	int sum=0;
    	for(int i=1;i<=N;i++){
    		if(sum+w[i]<=W) sum+=w[i];
    	}
    	if(sum<(int)ceil((W*1.0)/2.0)) cout<<"NO"<<'\n';
    	else cout<<"YES"<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/11/problem/710
[c70769545d9f44458a024424ba7352fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/70884cac5f8a45798cd6c81fb8f06cf1.png