题解：AT_abc431_c [ABC431C] Robot Factory

题意

要用

1

个头和

1

个身体组成机器人，头的重量要大于等于身体的重量。问能否组成

K

个不倒的机器人（每个部件只能用一次）。

思路

贪心的思路解决。

先最大化匹配成功率：将头部件和身体部件按重量从小到大排序，接下来我们要选取最轻的

K

个头部件和最重的

K

个体部件进行配对，让最轻的头配最重的体，次轻的头配次重的身体，依此类推。

最后判断，如果

K

对都满足头部件的重量不超过身体部件的重量，就能成功制作

K

个不倒的机器人，否则不能。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
int a[N],b[N];
void solve()
{
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	if(k>n||k>m){
		cout<<"No";
		return;
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+m);
	for(int i=1;i<=k;i++){
		if(a[i]>b[m-k+i]){//从前判断和从后判断
			cout<<"No";
			return;
		}
	}
	cout<<"Yes";
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	int _=1;//cin>>_;
	while(_--)solve();
	return 0;
}

题解：AT_abc431_c [ABC431C] Robot Factory

文章操作

题意

思路

代码

相关推荐

评论

题解：AT_abc431_c [ABC431C] Robot Factory