C语言贪心算法求解：P1825 东方香霖堂 题目描述 魔法之森里有一家道 (po) 具 (lan) 店，其名为香霖堂。 其店主，森近霖之助 (Morichika Rinnosuke)，决定给一些清仓商品打折。 具体地说，现在有 � N 个清仓商品，编号从 1 1 到 � N。编号为 � i 的商品的价格为 � [ � ] a[i] 元。 魔法之森里有一个（可怜的）金发小女孩，其名为魔理莎 (Marisa), 准备前去购买一些清仓商品用于炼药。 不过魔理莎穷困潦倒，只有 � K 元钱，而她又想买到尽可能多的物品。现在请你告诉她，她使用 � K 元最多能买到多少个物品。 输入格式 第一行：两个正整数 � N 和 � K。 第二行： � N 个正整数，第 � i 个数表示编号为 � i 的商品的价格为 � [ � ] a[i] 元。 输出格式 一行，一个正整数，表示使用 � K 元最多买到多少个物品。 输入样例 1 Copy to Clipboard 5 100 98 102 99 104 1 输出样例 1 Copy to Clipboard 2 输入样例 2 Copy to Clipboard 8 10 1 1 4 5 1 4 1 9 输出样例 2 Copy to Clipboard 5 数据规模 对于一部分数据，保证 � ≤ 10 , � ≤ 100 , � [ � ] ≤ 10 N≤10,K≤100,a[i]≤10。 对于所有数据，保证 � ≤ 1 0 4 , � ≤ 1 0 5 , � [ � ] ≤ 5000 N≤10 4 ,K≤10 5 ,a[i]≤5000。

以下是C语言贪心算法的代码实现：

#include <stdio.h>
#include <stdlib.h>

#define max_n 100005

typedef struct {
    int price;
    int num;
} Item;

int cmp(const void *a, const void *b) {
    return ((Item *)b)->price - ((Item *)a)->price;
}

int main() {
    int n, k;
    Item items[max_n];
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &items[i].price);
        items[i].num = 1;
    }
    qsort(items, n, sizeof(Item), cmp);
    int ans = 0;
    for (int i = 0; i < n && k >= items[i].price; i++) {
        int num = k / items[i].price;
        if (num > items[i].num) {
            num = items[i].num;
        }
        ans += num;
        k -= num * items[i].price;
    }
    printf("%d\n", ans);
    return 0;
}

首先将每个商品看作一个价值为1的物品，按照价格从高到低排序。在循环中，每次取一个价格最高的商品，判断魔理莎能否购买，如果能，就购买尽可能多的数量，并将购买的商品数量累加到答案中。最后输出答案即可。

需要注意的是，每个商品的数量可能不止1个，因此购买的数量不能超过商品的数量。