思路

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

代码

c++

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,k,m,sum;
ll a[N];
int main()
{
    cin>>n>>k>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
    {
        sum+=a[i]/k;
        a[i]%=k;
    }
    sort(a,a+n);
    for(int i=n-1;i>=0;i--)
        if(m>=(k-a[i]))
        {
            sum++;
            m-=(k-a[i]);
        }
    sum+=m/k;
    cout<<sum<<endl;
}

python

n, k, m = map(int, input().split())
a = list(map(int, input().split()))
sum = 0

for i in range(n):
    sum += a[i] // k
    a[i] %= k

a.sort()

for i in range(n - 1, -1, -1):
    if m >= (k - a[i]):
        sum += 1
        m -= (k - a[i])

sum += m // k
print(sum)

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        long k = scanner.nextLong();
        long m = scanner.nextLong();
        long sum = 0;

        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextLong();
        }

        for (int i = 0; i < n; i++) {
            sum += a[i] / k;
            a[i] %= k;
        }

        Arrays.sort(a);

        for (int i = n - 1; i >= 0; i--) {
            if (m >= (k - a[i])) {
                sum += 1;
                m -= (k - a[i]);
            }
        }

        sum += m / k;
        System.out.println(sum);
    }
}

题目内容

小红有$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