贪心法解决邮票套数问题

小北是一个远近闻名的画家和收藏邮票的爱好者。这天, 小北在整理他的邮票。
他一共有 n 种邮票, 第 i 种邮票上印有正整数i(i∈[1,n]), 且第 i 种邮票 现有 ai张。
而如果有 n 张邮票, 其中每种邮票各一张, 那么这 n 张邮票可以被称为一 套邮票。小北为了凑出尽可能多套邮票, 拿出了 m 张空白邮票, 他可以在上面写上数 i, 将其当做第 i 种邮票来凑出一套邮票。然而小北觉得手写的邮票不太美观, 决定第 i 种邮票最多手写 bi 张。
请问小北最多能凑出多少套邮票?


#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int max_sets = 0; // 最大可凑套数
    int max_i = 0; // 最大可凑套数时的手写邮票种类
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        int num_sets = min(a, b); // 当前邮票种类最多可凑套数
        if (num_sets > max_sets) { // 若可凑套数更多，则更新
            max_sets = num_sets;
            max_i = i;
        }
    }

    int num_extra = m - max_sets; // 剩余空白邮票数量
    if (num_extra < 0) { // 若空白邮票不够凑，则全部手写该种邮票
        max_sets = m;
    } else { // 否则，将多余的空白邮票分配给其他种类
        for (int i = 1; i <= n; i++) {
            if (i == max_i) continue; // 最大可凑套数时的手写邮票已经计算过了，跳过
            int a;
            cin >> a;
            int num_sets = min(a, m - max_sets); // 当前邮票种类最多可凑套数
            max_sets += num_sets; // 更新已凑套数
            if (max_sets == m) break; // 已凑够，退出循环
        }
    }

    cout << max_sets << endl;

    return 0;
}

望采纳

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int ans = 0, blank = m - n;
    for (int i = 1; i <= n && blank >= 0; i++) {
        int a;
        cin >> a;
        int sets = a / n;
        ans += sets;
        a -= sets * n;
        int additional = min(blank, min(a, n - 1));
        ans += additional / n;
        blank -= additional;
    }
    cout << ans << endl;
    return 0;
}