AT_abc441_c.[ABC441C] Sake or Water
普及-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有 N 个杯子,每个杯子都装有一种无色透明的液体。
具体来说,第 i 个杯子 (1≤i≤N) 中有 Ai 毫升液体。
众所周知,这些杯子中正好有 K 个装的是清酒(米酒),其余的装的是水。但是,不知道哪些杯子装的是清酒。高桥可以选择一些(一个或多个)杯子,喝掉其中的所有液体。
求无论哪些杯子装有清酒,在保证他至少喝 X 毫升清酒的前提下,他至少需要选择多少个杯子? 如果无法选择,请输出 −1 。
输入格式
输入内容由标准输入提供,格式如下:
N K X
A1 A2 … AN
输出格式
打印高桥为满足条件而需要选择的最少杯子数。如果无法选择,则输出 −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
考虑高桥选择第一杯和第三杯并喝下它们的情况。
三个杯子中有两个装的是清酒,因此可能出现以下三种情况:
- 如果第一杯和第二杯都有清酒
他喝了 10 毫升清酒和 8 毫升水。
- 如果第一杯和第三杯装的是清酒
他喝 18 毫升清酒。
- 如果第二和第三杯有清酒
他喝 8 毫升清酒和 10 毫升水。
因此,在所有情况下,他至少可以喝 5 毫升清酒。
另一方面,在不知道哪些杯子装清酒的情况下,只选择一个杯子是不可能满足条件的。因此,输出 2 。
样例解释 #2
如果第一杯装的是清酒,那么无论选择哪一杯,都不可能喝下 8 毫升或更多的清酒。
因此,输出 −1 。
数据范围
- 1≤K≤N≤3×105
- 1≤Ai≤109
- 1≤X≤3×1014
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?