思路

  此题实际上就是贪心加排序，想要购买到数量最多的物品，我们就要尽量让每一个钱包原本的钱不浪费，在每个钱包买完物品后会遗留一些钱x（0<=x<k），我们就将遗留的钱补足直至可以购买一个物品，则可以使钱不浪费，当然我们可支配的钱可能不够，所以要从遗留的钱更多的钱包开始不足，若能全部补足完，留下来的钱全部购买物品

代码

c++

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

题目内容

小红有$n$个钱包，其中第$i$个钱包装了$a_i$元，他每天都会恰好使用一个钱包中的钱去购物，尽可能多地购买一种单价为$k$元的物品，日复一日，直到所有钱包中的钱都分别买不起此物品。

在小红在开始日复一日地购物前，可以向任意一些钱包中再加入一些钱，但总共加入的钱数不超过$m$。

现在小红想知道，如果自己以最优方案向钱包中加钱，那么最多可以购买多少件此物品。

输入描述

第一行输入三个整数 $n,k$和$m$（$1≤n≤10^5;1≤k≤10^9；0≤m≤10^{14}$）表示小红的钱包个数，要购买的物品单价，以及小红最多可以提前加入钱包中的钱。

第二行输入$n$个正整数$a_1,a_2,...,a_n(1≤a_i≤10^9)$表示小红每个钱包的钱数。

输出描述

在一行输出一个整数，表示小红最多可以购买的此物品数量。

样例1

输入

5 3 2
4 4 3 1 2

输出

4

说明

可以提前向第五个钱包中加入$1$元，各个钱包变成[$4,4,3,1,3$]，此时用每个钱包日复一日购买这个单价为$3$的物品，显然最多可以买$4$个。

全都不能买时，各个钱包为：[$1,1,0,1,0$]

样例2

输入

3 10 0
9 6 3

输出

0