题目详情题解（0）讨论（0）提交记录（0）

AT_abc431_c.[ABC431C] Robot Factory

入门

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥可以将一个头部零件和一个身体零件组合起来制造一个机器人。如果头部零件的重量大于身体零件的重量，这个机器人就会倒下。

现在，他有 NN 个头部零件和 MM 个身体零件。第 ii 个（1≤i≤N1 \leq i \leq N）头部零件的重量为 HiH_i 克，第 ii 个（1≤i≤M1 \leq i \leq M）身体零件的重量为 BiB_i 克。

他想通过合理地组合手中的零件，制造出恰好 KK 个不会倒下的机器人。请你判断他能否通过合理组装，完成这个目标。

这里，每个零件只能用来制造一个机器人，且每个机器人只能由一个头部零件和一个身体零件组合而成，不能用多个头部零件或多个身体零件。

输入格式

输入按如下格式从标准输入读入：

NN MM KK H1H_1 H2H_2 …\ldots HNH_N B1B_1 B2B_2 …\ldots BMB_M

输出格式

如果高桥能够合理组合零件，制造出 KK 个不会倒下的机器人，输出 Yes；否则输出 No。

输入输出样例

  • 输入#1

    6 6 3
2 7 1 8 2 8
1 8 2 8 4 5

    输出#1

    Yes

  • 输入#2

    1 1 1
43
1

    输出#2

    No

  • 输入#3

    1 1 1
100
100

    输出#3

    Yes

  • 输入#4

    12 15 12
748 169 586 329 972 529 432 519 408 587 138 249
656 114 632 299 984 755 404 772 155 506 832 854 353 465 387

    输出#4

    Yes

说明/提示

样例解释 1

如果我们用 (i,j)(i, j) 表示将第 ii 个头部零件和第 jj 个身体零件组合，那么，例如通过组合 (1,2),(2,4),(3,6)(1,2),(2,4),(3,6)，高桥可以制造出三个不会倒下的机器人。

因此，输出 Yes。

样例解释 2

他的头部零件太重了，无法制造出任何不会倒下的机器人。

样例解释 3

注意，如果头部和身体重量相等，机器人也不会倒下。

数据范围

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤K≤min⁡{N,M}1 \leq K \leq \min\lbrace N, M\rbrace
  • 1≤Hi≤109 (1≤i≤N)1 \leq H_i \leq 10^9\ (1 \leq i \leq N)
  • 1≤Bi≤109 (1≤i≤M)1 \leq B_i \leq 10^9\ (1 \leq i \leq M)
  • 所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页