文章目录

题目描述输入输出样例输入样例输出C语言代码实现思路排序处理完整代码 C++代码实现排序完整代码 彩蛋

题目描述

小健有一家自己的商店，主营牛奶饮品，最近资金紧张，他想以尽可能低的价格进购足够的牛奶以供日常的需要。所以小健想要求助你帮他想出一个最好的节省资金的办法。 小健可以从几个农场里购买牛奶，每个农场的牛奶都有自己的价格，每天的供应量也是有限的。小健只可以从每个农场里购买整数量的牛奶，且数量要小于等于农场的最大供应量。 给你小健每天所需要的牛奶总量，以及每个农场牛奶的单价和最大供应量，请你计算一下小健最少花多少钱就可以满足自己的需求。 ps: 一定存在一个方案可以满足小健的需求。

---

输入

多组输入，读入到文件末。 每组的第一行两个整数N and M. 第一个数 N (0 <= N <= 2000000) 小健每天的牛奶需求量. 第二个数 M (0 <= M <= 5000) 小健可以选择购买的农场数. 每组的第二行到M+1行:每行两个整数 Pi and Ai. Pi (0 <= Pi <= 1000)农场i的牛奶单价. Ai (0 <= Ai <= 2000000)农场i的最大供应量.

---

输出

输出可以满足小健每天需求的最小钱数。

---

样例输入

100 5 5 20 9 40 3 10 8 80 6 30

---

样例输出

630

---

C语言代码实现

---

思路

思路其实很简单，做数学题嘛，先把每个农场的牛奶价格由低到高作升序排列，然后开始看第一个农场有的牛奶总量够不够小健的需求，不够的话再去第二个农场买嘛，直到买够为止。 拿这道题来讲： 1、先做价格的排序（同时仍要将牛奶量与之对应）

3 10 5 20 6 30 8 80 9 40

10+20+30+40=100 也就是买到第四行的时候不必将80个全买下来，买40个就够了

因此价格就等于10 * 3 + 20 * 5 + 30 * 6 + 40 * 8 = 630

---

排序

排序难点其实不在于排价格，价格从低到高排列，冒泡啊、插入啊、快排啊、都能解决，难点在于如何将价格排序的同时，将对应农场的牛奶量也进行相应的排序（因为采用的是两个数组分别存价格和牛奶量），但仔细一想，也不难。排价格数组的时候顺便把牛奶量数组的下标一改就行了。代码如下：

void sort(int* a,int* b) { for(int m = 1; m < M; m++){ int t = a[m]; int q = b[m]; for(int j=m;a[j]<a[j-1];j--){ a[j]=a[j-1]; a[j-1]=t; b[j]=b[j-1]; b[j-1]=q; } } }

---

处理

接下来就是简简单单的做小学数学题了。代码如下：

int deal(int N,int* P,int* A) { mon=0;//价格重置 for (int i = 0; i < M; i++) { int tmp = N < A[i]? N : A[i];//通过三目运算来择取剩余需求和农场i牛奶量之间的最小值 mon += tmp * P[i];//计算价格 N -= tmp;//重新处理剩余需求 } return mon;//最终返回所求的最低价格 }

---

完整代码

#include <iostream> #include <vector> using namespace std; int N,M;//N需求量，M农场数 #define num 5003 int P[num]; int A[num];//P牛奶单价，A最大供应量 int mon;//最低价格 int deal(int N,int* P,int* A) { mon=0;//价格重置 for (int i = 0; i < M; i++) { int tmp = N < A[i]? N : A[i];//通过三目运算来择取剩余需求和农场i牛奶量之间的最小值 mon += tmp * P[i];//计算价格 N -= tmp;//重新处理剩余需求 } return mon; } void sort(int* a,int* b) { for(int m = 1; m < M; m++){ int t = a[m]; int q = b[m]; for(int j=m;a[j]<a[j-1];j--){ a[j]=a[j-1]; a[j-1]=t; b[j]=b[j-1]; b[j-1]=q; } } } int main(int argc, char const *argv[]) { while (cin >> N >> M) { for (int i = 0; i < M; i++) { cin >> P[i]; cin >> A[i]; } sort(P,A); deal(N,P,A); cout << mon << endl; } return 0; }

---

C++代码实现

思路都一样，只是存储价格和牛奶量的方法不再局限于数组，可以使用容器vector和结构模板pair，以及不用自己实现sort函数，可以直接调用algorithm里的sort函数。（ps：当然c语言也有qsort函数，但是STL是真的香啊~）

---

排序

写一个compare函数的目的主要是为了便于自己理解sort函数的第三个参数，当然不写自定义函数直接将sort的第三个参数写成lambda表达式会更方便（也更难理解嘤嘤嘤）。哦此处提醒一下，从数学上来看，sort函数是一个左边闭区间，右边开区间的域，也就是如果有一个数组a[3]，用户想要给整个数组升序排序要写成sort(a,a+3)，众所周知a[3]是a+2，当然用容器就不牵扯这个问题了。

bool compare(pair<int,int> a,pair<int,int> b){ return a.first < b.first;//升序排列 }

---

完整代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; int N,M;//N需求量，M农场数 int mon;//最低价格 bool compare(pair<int,int> a,pair<int,int> b){ return a.first < b.first; } int main(int argc, char const *argv[]) { while (cin >> N >> M) { vector<pair<int,int>> data(M);//data存储牛奶单价(first)和最大供应量(second) for (int i = 0; i < M; i++) { cin >> data[i].first >> data[i].second; } sort(data.begin(),data.end(),compare); mon = 0; for (auto& tmp : data) { int num = N > tmp.second? tmp.second : N; mon += (num * tmp.first); N -= num; } cout << mon << endl; } return 0; }

---

彩蛋

不需要compare的sort长什么样呢？我明天就学lambda表达式好叭！

sort(res.begin(), res.end(),[](const pair<int, int>& cast1, const pair<int, int>& cast2){ return cast1.first < cast2.first; });