问题描述】 由于面粉产品利润很低,所以降低原材料小麦的收购价格就变得十分重要。帮助A公司找到最优的小麦采购方案。 A公司从一些农民手中采购小麦,并且每一位农民为这些工厂提供的价格是不同的。此外,每位农民每天能提供的小麦数量是一定的。每天A公司可以从农民手中采购到小于或者等于农民最大产量的整数数量的小麦。 给出A公司每天对小麦的需求量,还有每位农民提供的小麦单价和最高供应数量。计算采购满足需求的小麦所需的最小花费。 【输入形式】 第 1 行共二个数值:N,(0<=N<=2,000,000)是需要小麦的总数;M,(0<= M<=5,000)是提供小麦的农民个数。 第 2 到 M+1 行:每行二个整数:Pi 和 Ai。 Pi(0<= Pi<=1,000) 是农民 i 的小麦的单价。 Mi(0 <= Ai <= 2,000,000)是农民 i 一天能卖给A公司的小麦最大数量。 【输出形式】 单独的一行包含单独的一个整数,表示A公司拿到所需的小麦所需要的最小费用。 【样例输入】 100 5 5 20 9 40 3 10 8 80。通过c语言实现 写出源代码
时间: 2024-02-17 19:03:33 浏览: 29
```
#include <stdio.h>
#include <stdlib.h>
// 农民结构体
struct farmer {
int price; // 单价
int max_amount; // 最大供应量
};
// 比较函数,用于qsort排序
int cmp(const void *a, const void *b) {
struct farmer *f1 = (struct farmer *)a;
struct farmer *f2 = (struct farmer *)b;
return f1->price - f2->price;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
// 读入农民数据
struct farmer farmers[m];
for (int i = 0; i < m; i++) {
scanf("%d %d", &farmers[i].price, &farmers[i].max_amount);
}
// 按照单价从小到大排序
qsort(farmers, m, sizeof(struct farmer), cmp);
// 贪心算法,从单价最低的农民开始采购
int cost = 0;
for (int i = 0; i < m && n > 0; i++) {
if (n >= farmers[i].max_amount) {
// 如果需求量大于等于该农民的最大供应量,全部采购
cost += farmers[i].price * farmers[i].max_amount;
n -= farmers[i].max_amount;
} else {
// 否则只采购需求量的小麦
cost += farmers[i].price * n;
n = 0;
}
}
printf("%d\n", cost);
return 0;
}
```