题目大意
多组询问，有$n$个物品，每个物品有占用体积$a$，同时占用过后会归还一部分体积$b$，询问能否将所有物品选完。
对于1~4个测试点，T=10,1≤n≤9,1≤V≤100000,0≤a,b≤100000
对于5~8个测试点，T=20,1≤n≤1000,1≤V≤100000,0≤a,b≤100000
对于9~12个测试点，T=5,1≤n≤100000,1≤V≤1000,0≤a,b≤1000
对于13~16个测试点，T=500,1≤n≤1000,1≤V≤100000,0≤a,b≤100000
对于17~20个测试点，T=8,1≤n≤50000,1≤V≤100000,0≤a,b≤100000
题目分析
根据数据范围与题意，不难发现这不是动态规划能够解决的问题。
只剩下一种方法：贪心。
不难发现，我们肯定是先选择物品$x$满足$x.a\le x.b$的。
那么对于物品满足$a\le b$的条件，若全部选完，体积是一定的，因此我们应该尽量地满足能选到当前物品。不难发现，当满足$x.a<y.a$时是最优的。
当$x.a\gt x.b$的，很难想出一个有效的贪心方式，不如反过来思考，假设能选完所有物品（选不完我们不讨论），那么我们所有的条件都反过来，就变成上面的贪心了。可以发现，当满足$x.b>y.v$是最优的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
struct Thing {
int a,b;
bool operator < (const Thing& x) const {
if((a<b&&x.a>x.b)||(a>b&&x.a<x.b))return b-a>x.b-x.a;
if(a<b)return a<x.a;
return b>x.b;
}
} a[100005];
int t,n;
LL v;
int main() {
t=Get_Int();
while(t--) {
n=Get_Int();
v=Get_Int();
for(int i=1; i<=n; i++) {
a[i].a=Get_Int();
a[i].b=Get_Int();
}
sort(a+1,a+n+1);
bool bj=1;
for(int i=1; i<=n; i++) {
if(v<a[i].a) {
bj=0;
puts("No");
break;
}
v=v-a[i].a+a[i].b;
}
if(bj)puts("Yes");
}
fclose(stdin);
fclose(stdout);
return 0;
}
|
