题目描述

有N栋房屋待售，其中第i栋房屋的售价为$ A_i $美元。

你的购买房屋预算为B美元。

请问你最多可以购买多少栋房屋。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据占两行，第一行包含整数N和B。

第二行包含N个整数，其中第i个数表示第i个房屋的售价$ A_i $。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为Case #x: y，其中x为组别编号（从 1 开始），y 为能够购买的房屋最大数量。

数据范围

$ 1≤T≤100 $,
$ 1≤B≤10^5 $,
$ 1≤A_i≤1000 $,
$ 1≤N≤10^5 $

样例

输入样例：

3
4 100
20 90 40 90
4 50
30 30 10 10
3 300
999 999 999

输出样例：

Case #1: 2
Case #2: 3
Case #3: 0

算法1

(计数排序) $O(n)$

• 本题看样子很简单，直接排序枚举就可以了，但Acwing怎么可能让你这么容易过掉呢

• 因为该数据范围最大值较小，引入计数排序即可将复杂度降为O(n)

  • 计数排序的原理为，从该数组最小数枚举到最大数，记录其个数，然后输出即为排序结果

时间复杂度

计数排序为o(n),所以总的时间复杂度即为o(n)。

参考文献

Google KickStart

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;

int n, b;
int a[N];

void count_sort(int data[], int length)
{
    if (data == nullptr || length <= 0)
        return;

    //确定数列最大值
    int maxn = data[0];
    for (int i = 1; i < length; ++i){
        if (data[i] > maxn)
            maxn = data[i];
    }
    // 确定统计数组长度并进行初始化
    int* coutData = new int[maxn + 1];
    for (int i = 0; i <= maxn; ++i)
        coutData[i] = 0;
    // 遍历数组，统计每个数出现的次数
    for (int i = 0; i < length; ++i)
        ++coutData[data[i]];
    // 排序数组，某个数出现了几次，便在data里累计输出几次
    int index = 0;
    for (int i = 0; i <= maxn; ++i)
        for (int j = 0; j < coutData[i]; ++j)
            data[index++] = i;
    delete coutData;
}

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T--){
        cin >> n >> b;
        for(int i = 0; i < n; i++) cin >> a[i];
        count_sort(a, n);
        int res = 0;

        for(int i = 0; i < n; i++){
            if(b >= a[i]){
                b -= a[i];
                res ++;
            }
        }

        printf("Case #%d: %d\n", cnt ++, res);
    }
    return 0;
}