题解：AT_abc431_c [ABC431C] Robot Factory

Fake_Cry · 2025-11-28 19:17:18 · 题解

题意

要用 1 个头和 1 个身体组成机器人，头的重量要大于等于身体的重量。问能否组成 K 个不倒的机器人（每个部件只能用一次）。

思路

贪心的思路解决。

先最大化匹配成功率：将头部件和身体部件按重量从小到大排序，接下来我们要选取最轻的 K 个头部件和最重的 K 个体部件进行配对，让最轻的头配最重的体，次轻的头配次重的身体，依此类推。

最后判断，如果 K 对都满足头部件的重量不超过身体部件的重量，就能成功制作 K 个不倒的机器人，否则不能。

代码

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