题目描述

cc最近收到了好多礼物，对着满地大小不一的礼物，她想要一个包来装，于是dd就掏出了一个会说话的神奇背包给cc装礼物。
cc为了一次性装尽可能多的礼物，于是跟这个背包定下了一个规则，对每个礼物，背包会给出它对这件礼物的喜爱程度，背包越喜欢这个礼物，它就会越开心，越开心，它就会扩大自己的容量。
于是问题就变成了这样：每个礼物都有自己的体积ai，背包也会给出它对这些礼物的喜爱程度bi，并且为了方便cc计算，背包告诉cc，喜爱程度bi就是这件物体放进背包，背包后会扩大的体积。
那么现在cc想知道，对这一地的礼物，有没有某种放的顺序，可以一次性把所有礼物都放进包里？
当然，物体要先放进背包，背包才会扩大自己的体积
比如当前背包的剩余体积为2，礼物的体积为3，喜爱程度为4，也是不能放进背包的。

输入描述:

输入包含多组数据，第一行为一个整数T(1<=T<=20)
每组数据第一行包含两个整数n,v(1<=n,v<=1000)表示共有n个礼物，背包一开始的体积为v
接下去的n行每行包含两个整数ai,bi(1<=ai,bi<=1000)表示每个礼物的体积ai与背包对这件礼物的喜爱程度bi
1 <= T <= 20
1 <= n, v <= 100000
1 <= ai, bi <= 100000

输出描述:

若存在一种放礼物的顺序可以让cc把所有礼物放进背包，则输出"yes"否则输出"no"（引号不包含在内）
示例1
输入
复制
1
4 2
1 2
2 1
3 1
2 3
输出
复制
yes

题解:

首先，这是一道贪心题。。。我们可以优先选择使背包容量增大的礼物。
如果用c表示礼物对背包容量的影响（c = b - a,显然为正则加容量，为负则减容量）。
首先我们考虑一种情况，将所有的影响加起来，再加上初始容量v，记为space，
则space表示的是不考虑限制把所有礼物都放进背包时，背包最后的容量，如果这种情况下space都为负，
则不必加限制我们就能判定此时不能满足题意。而我们先放入增加容量的礼物，最后放入减容量的礼物，
这时候如果space>0,我们可不必考虑减容量的礼物，因为既然结果space>0,先将容量加到最大后一定够减。
所以我们只考虑space>0时只考虑加容量的礼物即可；
存放顺序：先放体积小的，相同则先放增益大的；

#include <iostream>
 #include <algorithm>
 using namespace std;
 const int MXN=1e7+5;
 int t,n,v,num,flag;
 // t数据组数 n礼物总数 v初始容量 num正增益礼物数 flag记录结果 
 long long space;
 // 最后容量 
 struct dot{
    int a,b,c;
 }A[MXN];
 bool cmp(dot p,dot q){
    if(p.a!=q.a) return p.a < q.a;
    return p.b > q.b;
 }
 int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&v);
        space = v;
        num = 0;
        for(int i = 0;i < n;i++){
            int a,b,c;
            scanf("%d %d",&a,&b);
            c = b - a;
            space += c;
            if(c > 0){
                A[num].a = a;
                A[num].b = b;
                A[num].c = c;
                num++;    
            }
        }
        sort(A,A+num,cmp);
        flag = 0;
        if(space < 0) flag = 1;
        else
            for(int i = 0;i < num;i++){
                v -= A[i].a;
                if(v<0){
                    flag = 1;
                    break;
                }else{
                    v += A[i].b;
                }
            }
        if(flag) printf("no\n");
        else printf("yes\n");
    }


    return 0;
}

第一次写题解，点个赞支持一下吧！