返回首页 返回题库

做题

C++ 简单 GESP四级真题 #排序#贪心

题目描述

题面描述

小杨同学为了提高自己的实力制定了做题计划,在第 k 天时,他必须要完成 k 道题,否则他就会偷懒。

小杨同学现在找到了一个题库,一共有 n 套题单,每一套题单中有一定数量的题目。但是他十分挑剔,每套题单他只会使用一次,每一天也只能使用一套题单里的题目,之后那套题单就会被弃之不用。对于每套题单,他不必完成题单内所有的题。

那么问题来了,小杨同学最多会做题几天才偷懒呢?

输入格式

第一行,1个数为 n,表示有多少套题单。

第二行,n 个整数 ,分别表示每套题单有多少道题。

输出格式

输出一行,小杨同学偷懒前最多做题天数。

样例1

输入:

4
3 1 4 1

输出:

3

样例2

输入:

5
2 2 2 2 2

输出:

2

数据范围

对于全部数据,保证有 。

时间限制

1秒

内存限制

256MB

💡 查看提示(先自己想一想再看)
本题考察贪心算法与排序的应用,核心思路是将题单按题目数量从小到大排序,依次匹配每天需要的题量:要满足第k天需要k道题,应该优先用最小的能满足要求的题单,这样更大的题单可以留给后续需要更多题量的天数。注意数据范围较大,需要使用高效的排序算法,数组可以用long long类型避免溢出。
⚙ 开始做这道题 0 人做过 · 0 收藏 · 7 浏览

讨论(0)