题解：AT_abc431_c [ABC431C] Robot Factory
chenzefan
·
·
题解
题目传送门
## 思路
题目要求做到 $O(\max(N,M))$。
下文中 $i$ 是 $H$ 数组的下标。$j$ 是 $B$ 数组的下标。
考虑**双指针**，先对 $H_i$ 和 $B_j$ 升序排序。则有对于数对 $(i,j)$，若其不满足条件。则 $(i,k)(k \in [1,j-1])$ 都不满足条件。
直接考虑对于每个 $i$，去往后找第 $1$ 个可行的 $j$，满足题目的要求，即 $B_j \ge H_i$。每次找到后 $i$ 和 $j$ 都往右移动。没找到输出 `No`。时间复杂度为寻找 $j$ 的 $O(M)$。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,m,k,a[N],b[N],cnt;
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%lld",a+i);
for(int i=1;i<=m;i++) scanf("%lld",b+i);
sort(a+1,a+n+1);sort(b+1,b+m+1);
int i=1,j=1;
while(i<=n&&j<=m){
while(j<=m&&b[j]<a[i]) j++;
if(j>m) break;
i++;j++;
if(++cnt==k) return printf("Yes"),0;
}printf("No");
return 0;
}
```
撒花！