题解：AT_abc431_c [ABC431C] Robot Factory

· · 题解

题意概述： 每个机器人由一个头部零件和一个身体零件组成，如果头部的重量大于身体的重量，则机器人会摔倒。现有 N 个头部零件和 M 个身体零件，并给定长度为 N 的数组 H 和长度为 M 的数组 B 表示其重量。求是否能组成 K 个不摔倒的机器人。

Solution

贪心思想，读入后对两个数组进行排序，始终用最轻的头对最轻的身体。用 ans 变量记录配对成功的机器人数量，匹配结束后与 K 进行比较，输出答案。

具体解释见代码。

#include<bits/stdc++.h>
using namespace std;

const int maxn=200005;
int h[maxn],b[maxn];

int main(){
    int n,m,k;
    cin>>n>>m>>k;

    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=m;i++) cin>>b[i];//读入

    sort(h+1,h+n+1);
    sort(b+1,b+m+1);//排序

    int op=1,ans=0;//op表示身体零件使用到的位置

    for(int i=1;i<=n;i++){//头部用完则结束匹配
        while(h[i]>b[op] && op<=m) op++;
        if(op==m+1) break;//身体用完则结束匹配
        else op++,ans++;
    }

    if(ans>=k) cout<<"Yes";
    else cout<<"No";//判断并输出

    return 0;
}

//Terabyte's code.