题目描述
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; }
第一次写题解,点个赞支持一下吧!