一、题目内容

题目描述

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

二、解题思路

这道题很明显，背包拥有限制值和期望值，限制值是他的体积V（V可以根据礼物的体积和喜好增加或减少），期望值是它要尽可能地装完所有的礼物（装最多的礼物）。很明显的贪心算法应用的例子，遇到大部分类似的情况，我们都倾向于使用贪心算法去解决。因此，在礼物入背包时，我们优先选择可以增加背包容量的礼物，然后用来增加背包容量，用来满足会减小背包容量的礼物，这个过程就保证了尽可能的满足背包放进的礼物最多，假如背包容量不够，即不能够放进所有礼物。

注意，贪心算法的前提是前一步的选择不会影响后一步的决定。

代码实操

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int a,b,c;
    bool friend operator < (Node n, Node m) {
        return n.a == m.a ? (n.b > m.b) : (n.a < m.a);
    }
}s[100010];
//优化读入速度
inline void read(int &x) {
    x = 0; int c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
}

int main() {
    int T;
    read(T);
    while(T--) {
        int n,v;
        read(n);read(v);
        int num = 0;
        long long space = v;
        for(int i = 0; i < n; i++) {
            int a,b,c;
            read(a);read(b);
            c = b - a;
            if (c > 0) {
                s[num].a = a;
                s[num].b = b;
                s[num].c = c;
                num++;
            }
            space += c;
        }
        bool can = 1;
        //空间最终为负值，则不满足装满所有礼物的要求
        if (space < 0) {
            can = 0;
        } else {
            sort(s, s + num);
            for(int i = 0; i < num; i++) {
                if (v < s[i].a) {
                    can = 0;
                    break;
                }
                v += s[i].c;
            }
        }
        if (can) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }
    return 0;
}

最后编辑于：2019.11.27 16:44:34