题目描述

有N个数，权值为1，花费为 Ai ，现有预算B，求最大能选到多少个数

样例

3
4 100               OUTPUT
20 90 40 90         //Case #1: 2
4 50                //Case #2: 3
30 30 10 10         //Case #3: 0
3 300
999 999 999

算法1

思路
贪心，每次选花费最低的就好了
优先队列，最大堆MAX HEAP

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        int n, b;
        priority_queue<int, vector<int>, greater<int>> q;
        scanf("%d%d", &n, &b);
        int k;
        for (int i = 0; i < n; i++) {
            scanf("%d", &k);
            q.push(k);
        }
        int ans = 0;
        while (!q.empty()) {
            k = q.top();
            if (k <= b) {
                b -= k;
                ans++;
            } else {
                break;
            }
            q.pop();
        }
        printf("Case #%d: %d\n", t, ans);
    }
    return 0;
}