问题描述】 由于面粉产品利润很低,所以降低原材料小麦的收购价格就变得十分重要。帮助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 08:04:08 浏览: 10
这里提供一种贪心算法的实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int price;
int amount;
} Farmer;
int cmp(const void *a, const void *b) {
return ((Farmer*) a)->price - ((Farmer*) b)->price;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
Farmer farmers[m];
for (int i = 0; i < m; i++) {
scanf("%d%d", &farmers[i].price, &farmers[i].amount);
}
qsort(farmers, m, sizeof(Farmer), cmp);
int cost = 0;
for (int i = 0; i < m && n > 0; i++) {
int buy = n < farmers[i].amount ? n : farmers[i].amount;
cost += buy * farmers[i].price;
n -= buy;
}
printf("%d\n", cost);
return 0;
}
```
首先定义一个结构体 `Farmer` 表示每个农民的单价和最大供应量。然后读入输入并按照单价从小到大排序。接着从单价最小的开始遍历,每次尽量购买当前农民可供应的最大数量,直到满足需求为止。最后输出花费即可。