由于面粉产品利润很低,所以降低原材料小麦的收购价格就变得十分重要。帮助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 【样例输出】 630设计一个c语言代码
时间: 2024-02-17 10:02:26 浏览: 33
以下是基于贪心算法的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义结构体表示每个农民信息
typedef struct farmer {
int price; // 单价
int max_amount; // 最大供应量
} farmer;
// 比较函数,用于qsort排序
int cmp(const void* a, const void* b) {
farmer* fa = (farmer*)a;
farmer* fb = (farmer*)b;
return fa->price - fb->price;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
farmer* farmers = (farmer*)malloc(sizeof(farmer) * m);
for (int i = 0; i < m; i++) {
scanf("%d%d", &farmers[i].price, &farmers[i].max_amount);
}
// 按单价从小到大排序
qsort(farmers, m, sizeof(farmer), cmp);
int total_cost = 0;
for (int i = 0; i < m && n > 0; i++) {
int amount = farmers[i].max_amount < n ? farmers[i].max_amount : n;
total_cost += amount * farmers[i].price;
n -= amount;
}
printf("%d\n", total_cost);
free(farmers);
return 0;
}
```
该算法思路如下:首先将农民按单价从小到大排序,然后从单价最低的农民开始采购小麦,直到采购数量满足需求或者所有农民的最大供应量都被用尽。这样可以保证采购的成本最低。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)