P3845.第2题-奖项设置

1000ms

Difficulty: 5

所属公司 : 华为

算法与标签>贪心算法

题目内容

部门准备了一批奖品用于举办抽奖活动，奖品的价值为给定的正整数数组 $values$ ，其中 $values[i]$ 表示第 $i$ 个奖品的价值。

每位获奖者可以选择不限个数最大价值 $limit$ 的奖品组合，获奖者选择奖品的策略为在 $limit$ 限制内优先选择单价最高的奖品，请计算最少可以设置多少个奖项；

第一行：正整数 $len$ ，表述奖品价值数组 $values$ 的长度， $1<=len<=10^4$ ；

第二行：正整数数组 $values$ ，长度为 $len$ ，其中 $values[i]$ 表示第 $i$ 个奖品的价值， $1<=values[i]<=10^4$ ；

第三行：正整数 $limit$ ，表示每个获奖者可以获得的最大奖品价值， $1<=limit<=10^4$ 。

整数，代表本次抽奖活动可以设置最少的奖项数量；

输入

2
1 2
3

输出

说明

获奖者选择价值为 $1$ 和 $2$ 的两个奖品，最少可以设置 $1$ 个奖项

输入

7
13 4 4 3 3 5 5
12

输出

说明

获奖者 $1$ 选取价值为 $(5,5)$ 的奖品组合，获奖者 $2$ 选取价值为 $(4,4,3)、3$ 的奖品组合，因此：最少可以设置 $3$ 个奖项才能满足所有获奖者的领取诉求

输入

预期输出（选填）