【NOIP2017提高A组模拟9.5】NYG的背包

本文主要是介绍【NOIP2017提高A组模拟9.5】NYG的背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

输入1：
3 5
3 1
4 8
8 3

输入2：
3
7 9269
21366 1233
7178 23155
16679 23729
15062 28427
939 6782
24224 9306
22778 13606
5 22367
17444 5442
16452 30236
14893 24220
31511 13634
4380 29422
7 18700
25935 4589
24962 9571
26897 14982
20822 2380
21103 12648
32006 22912
23367 20674

Sample Output

输出1：
Yes

输出2：
Yes
Yes
No

Solution

各种奇奇怪怪的贪心都能拿很高分
首先对于会使背包变大的直接加入即可
对于剩下的呢？
题解的方法是按照b排序，从小到大加入
就是假设为yes那么放入等于删除，然后就-b+a，然后就和第一种情况一样了，因为第一种情况是-a+b，结果为正数，这个-b+a结果为正数

我的做法不太一样
大概是：
对于每种物品，它对m的贡献是-a+b，一个负数
而最后一个放入背包的物品的贡献是-a
如果m去掉了所有物品的贡献，仍然大于等于0，说明是yes
那么最后一个就一定是b最小的一个，因为我要使贡献减小的尽可能少，最后一个相比其他多减了一个b，那么选最小的b，减少的就最小
正确性好像是对的吧
（如果不正确欢迎大神打脸）

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 50100
#define ll long long
using namespace std;
int n;
struct node{ll x,y;
}a[N],b[N];
ll m;
bool cnt(node x,node y){return x.x<y.x;}
bool cmt(node x,node y){return x.y>y.y;}
int main()
{freopen("backpack.in","r",stdin);freopen("backpack.out","w",stdout);int ac;scanf("%d",&ac);for(;ac;ac--){scanf("%d%lld",&n,&m);int t1=0,t2=0;fo(i,1,n){ll x,y;scanf("%lld%lld",&x,&y);if(x<=y) a[++t1].x=x,a[t1].y=y;else b[++t2].x=x,b[t2].y=y;}sort(a+1,a+t1+1,cnt);bool bz=1;fo(i,1,t1) if(m>a[i].x) m=m-a[i].x+a[i].y;else bz=0;if(bz==0) {printf("No\n");continue;}sort(b+1,b+t2+1,cnt);ll jy=0;fo(i,1,t2) jy=jy-b[i].y+b[i].x;if(m>=jy) printf("Yes\n");else printf("No\n");}
}

这篇关于【NOIP2017提高A组模拟9.5】NYG的背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---