题目大意
题目分析
又是一道比较神奇的贪心。
首先二分答案应该是比较容易想到的。
二分答案后转为判定性问题。
开始想了一个错误的贪心思路：一个机器人肯定选取比自己小的更大的$mid$个元素。
这个思路看似正确，但因为有两个属性的影响，重量较小的可能体积更大，舍弃了这些较小的有可能使得该物品无法选取从而判断失误。
因此得出另一个贪心思路，优先选取重量比自己小的体积最大的$mid$个元素，这样便能保证最优。
那么我们用一个大根堆来维护决策。
最后需要卡卡常数才能过，所以说二分上界与$10000$取了个$\min$。
代码
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int 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 w,s;
bool operator < (const Thing& b) const {
return w<b.w;
}
} t[1000005];
int n,A,B,a[50005],b[50005];
bool Check(int mid) {
priority_queue<int>Q;
int j=1;
for(int i=1; i<=A; i++) {
while(j<=n&&t[j].w<a[i])Q.push(t[j++].s);
int cnt=mid;
while(cnt>0&&!Q.empty()) {
Q.pop();
cnt--;
}
}
while(j<=n)Q.push(t[j++].s);
for(int i=B; i>=1; i--) {
int cnt=mid;
while(cnt>0&&!Q.empty()&&Q.top()<b[i]) {
Q.pop();
cnt--;
}
}
return Q.empty();
}
int main() {
n=Get_Int();
A=Get_Int();
B=Get_Int();
for(int i=1; i<=A; i++)a[i]=Get_Int();
for(int i=1; i<=B; i++)b[i]=Get_Int();
for(int i=1; i<=n; i++) {
t[i].w=Get_Int();
t[i].s=Get_Int();
}
sort(a+1,a+A+1);
sort(b+1,b+B+1);
sort(t+1,t+n+1);
int Left=0,Right=min(n,10000);
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(Check(mid))Right=mid-1;
else Left=mid+1;
}
if(Left==n+1)puts("-1");
else printf("%d\n",Left);
return 0;
}
|
