题解 | #喆神装书#

题目描述：又是一年省赛，喆神收拾各种算法书要去打比赛了，但他最多只能背两个背包，而算法书分散在好几个背包里（zhe神有钱），他想知道，最后是否能够把所有的书都放在两个背包里。

输入描述：第一行一个数n，表示背包的数量。（0 <= n <=100）；第二行n个数$a_{i}a\_i$，分别表示每个背包里的书的个数。(0 <= $a_{i}a\_i$ <= 10000)；第三行n个数bi，分别表示每个背包的背包容量。(0 <= bi <= 10000)。

输出描述：如果可以把所有的书放在两个背包里，输出“YES”（没有引号）。否则，输出“NO”。

输入:
2
3 5
3 6
输出:
YES

联系博主：有任何问题可发送邮件到邮箱jiejaitt@foxmail.com或者添加qq/微信 jiejaitt 向我发起讨论

#include <bits/stdc++.h>
using namespace std;
int q[100];
// 感觉不是很像背包DP,注意不要开两个数组浪费空间
// 喆神最多只能背两个背包,只要最大容量的两个背包比书的总量多，就可以全部装下所有书
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    
    int n;cin>>n;
    int sum=0;
    // 书的总数
    for(int i=0;i<n;i++) {cin>>q[i];sum+=q[i];}
    for(int i=0;i<n;i++) cin>>q[i];
    sort(q,q+n);
    int res;
    if(n>=1) res=q[n-1]+q[n-2];
    if(res>sum) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define N 100
using ll=long long;
// 快读模板 竞赛佬常用
template <typename T> void read(T&x){
    x=0;
    ll f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    x*=f;
}
ll v[N];

int main(void){
    int n,w,flag=0;
    read(n);
    ll Maxw=0;
    for(int i=1;i<=n;i++) read(w),Maxw+=w;
    for(int i=1;i<=n;i++) read(v[i]);
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            if(v[i]+v[j]>=Maxw) {flag=1;break;}
        }
    } 
    if((n==1&&v[1]>=Maxw)||flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}