题解：AT_abc431_c [ABC431C] Robot Factory

题目传送门

\text{Update 2025/11/18}

时间复杂度瓶颈在排序，应为

O(N \log N+M \log M)

。

思路

题目要求做到

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;
}

撒花！

题解：AT_abc431_c [ABC431C] Robot Factory

文章操作

思路

代码

相关推荐

评论

题解：AT_abc431_c [ABC431C] Robot Factory