AT_abc441_c.[ABC441C] Sake or Water

普及-

通过率:0%

AC君温馨提醒

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

题目描述

有 NN 个杯子,每个杯子都装有一种无色透明的液体。

具体来说,第 ii 个杯子 (1≤i≤N)(1\leq i\leq N) 中有 AiA_i 毫升液体。

众所周知,这些杯子中正好有 KK 个装的是清酒(米酒),其余的装的是水。但是,不知道哪些杯子装的是清酒。高桥可以选择一些(一个或多个)杯子,喝掉其中的所有液体。

求无论哪些杯子装有清酒,在保证他至少喝 XX 毫升清酒的前提下,他至少需要选择多少个杯子? 如果无法选择,请输出 −1-1 。

输入格式

输入内容由标准输入提供,格式如下:

NN KK XX\\
A1A_1 A2A_2 …\ldots ANA_N

输出格式

打印高桥为满足条件而需要选择的最少杯子数。如果无法选择,则输出 −1-1 。

输入输出样例

  • 输入#1

    3 2 5
    10 6 8

    输出#1

    2
  • 输入#2

    2 1 8
    6 10

    输出#2

    -1
  • 输入#3

    5 3 3000000000
    1000000000 1000000000 1000000000 1000000000 1000000000

    输出#3

    5

说明/提示

样例解释 #1

考虑高桥选择第一杯和第三杯并喝下它们的情况。

三个杯子中有两个装的是清酒,因此可能出现以下三种情况:

  • 如果第一杯和第二杯都有清酒

他喝了 1010 毫升清酒和 88 毫升水。

  • 如果第一杯和第三杯装的是清酒

他喝 1818 毫升清酒。

  • 如果第二和第三杯有清酒

他喝 88 毫升清酒和 1010 毫升水。

因此,在所有情况下,他至少可以喝 55 毫升清酒。

另一方面,在不知道哪些杯子装清酒的情况下,只选择一个杯子是不可能满足条件的。因此,输出 22 。

样例解释 #2

如果第一杯装的是清酒,那么无论选择哪一杯,都不可能喝下 88 毫升或更多的清酒。

因此,输出 −1-1 。

数据范围

  • 1≤K≤N≤3×1051 \leq K \leq N \leq 3\times 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • 1≤X≤3×10141 \leq X \leq 3\times 10^{14}
  • 所有输入值均为整数。

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

首页