零花钱(贪心策略)

解题思路:

1.首先处理面额大于等于 m 的硬币，每枚可直接支付一周，直接累加数量。

2.对面额小于 m 的硬币，按面额从大到小排序，优先使用大面额硬币组合凑钱。

3.每次循环尝试凑出 m 元：

        先用大面额硬币尽可能填充，减少剩余金额。

        若仍有缺口，用一枚最小可能的大面额硬币补足。

        若无法凑齐，则停止计算。

4.累加所有能凑齐 m 元的次数，得到总星期数。

注意事项:

参考代码:

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

// 定义常量N，用于结构体数组的大小限制
const int N = 1e2 + 10;

// 结构体存储硬币的数量和面额
struct node{
    int qty;  // 该面额硬币的数量
    int coin; // 硬币的面额
} a[N]; 

// 全局变量定义
int n, m, ans, j;
// n：硬币种类数；m：每周需要的零花钱金额
// ans：最终能支付的星期数；j：有效硬币（面额小于m的）数量

// 排序比较函数：按硬币面额从大到小排序
bool cmp (node x, node y){
    return x.coin > y.coin;
}

int main()
{
    cin >> n >> m;  // 输入硬币种类数和每周所需金额
    
    for(int i = 0; i < n; ++ i){
        int c, q;
        cin >> c >> q;  // 输入硬币面额和数量
        
        // 如果硬币面额大于等于每周所需金额，每枚硬币可单独支付一周
        if(c >= m){
            ans += q;  // 直接累加可支付的星期数
            continue;  // 跳过后续处理，不存入数组a
        }
        
        // 面额小于m的硬币，存入数组a中
        a[j].coin = c;
        a[j].qty = q;
        j ++;  // 有效硬币数量加1
    }
    
    // 按面额从大到小排序，便于优先使用大面额硬币凑钱
    sort(a, a + j, cmp);
    
    // 循环计算用小面额硬币（需组合）能支付的星期数
    while(true){
        int r = m;  // r表示当前还需要凑齐的金额
        
        // 第一步：用大面额硬币尽可能凑齐剩余金额
        for(int i = 0; i < j; ++ i){
            // 如果当前硬币面额小于等于剩余金额，且还有库存
            if(a[i].coin <= r && a[i].qty > 0) {
                // 尽可能多地使用当前面额硬币
                while(a[i].qty > 0 && a[i].coin <= r){
                    r -= a[i].coin;  // 减少剩余金额
                    a[i].qty --;     // 减少当前硬币库存
                }		
            }
        }
        
        // 第二步：如果仍有剩余金额未凑齐，尝试用一枚大面额硬币补足
        if (r > 0){
            // 从面额小的硬币开始查找（避免浪费大面额）
            for(int i = j - 1; i >= 0; i --){
                // 如果找到面额大于等于剩余金额且有库存的硬币
                if(a[i].coin >= r && a[i].qty > 0){
                    r -= a[i].coin;  // 用这枚硬币补足剩余金额
                    a[i].qty --;     // 减少该硬币库存
                    break;           // 只需要一枚，跳出循环
                }
            } 
        }
        
        // 如果经过两步仍未凑齐金额，说明无法再支付一周，退出循环
        if(r > 0) break;
        
        // 成功凑齐一周的金额，累加星期数
        ans ++;
    }
    
    // 输出最终能支付的总星期数
    cout << ans;
    return 0;
}