文章目錄

• 題目描述
• 輸入
• 輸出
• 樣例輸入
• 樣例輸出
• C語(yǔ)言代碼實(shí)現(xiàn)
• • 思路
  • 排序
  • 處理
  • 完整代碼
• C++代碼實(shí)現(xiàn)
• • 排序
  • 完整代碼
• 彩蛋

題目描述

小健有一家自己的商店，主營(yíng)牛奶飲品，最近資金緊張，他想以盡可能低的價(jià)格進(jìn)購(gòu)足夠的牛奶以供日常的需要。所以小健想要求助你幫他想出一個(gè)最好的節(jié)省資金的辦法。
小健可以從幾個(gè)農(nóng)場(chǎng)里購(gòu)買(mǎi)牛奶，每個(gè)農(nóng)場(chǎng)的牛奶都有自己的價(jià)格，每天的供應(yīng)量也是有限的。小健只可以從每個(gè)農(nóng)場(chǎng)里購(gòu)買(mǎi)整數(shù)量的牛奶，且數(shù)量要小于等于農(nóng)場(chǎng)的最大供應(yīng)量。
給你小健每天所需要的牛奶總量，以及每個(gè)農(nóng)場(chǎng)牛奶的單價(jià)和最大供應(yīng)量，請(qǐng)你計(jì)算一下小健最少花多少錢(qián)就可以滿(mǎn)足自己的需求。
ps: 一定存在一個(gè)方案可以滿(mǎn)足小健的需求。

---

輸入

多組輸入，讀入到文件末。
每組的第一行兩個(gè)整數(shù)N and M.
第一個(gè)數(shù) N (0 <= N <= 2000000) 小健每天的牛奶需求量. 第二個(gè)數(shù) M (0 <= M <= 5000) 小健可以選擇購(gòu)買(mǎi)的農(nóng)場(chǎng)數(shù).
每組的第二行到M+1行:每行兩個(gè)整數(shù) Pi and Ai.
Pi (0 <= Pi <= 1000)農(nóng)場(chǎng)i的牛奶單價(jià).
Ai (0 <= Ai <= 2000000)農(nóng)場(chǎng)i的最大供應(yīng)量.

---

輸出

輸出可以滿(mǎn)足小健每天需求的最小錢(qián)數(shù)。

---

樣例輸入

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

---

樣例輸出

630

---

C語(yǔ)言代碼實(shí)現(xiàn)

---

思路

思路其實(shí)很簡(jiǎn)單，做數(shù)學(xué)題嘛，先把每個(gè)農(nóng)場(chǎng)的牛奶價(jià)格由低到高作升序排列，然后開(kāi)始看第一個(gè)農(nóng)場(chǎng)有的牛奶總量夠不夠小健的需求，不夠的話再去第二個(gè)農(nóng)場(chǎng)買(mǎi)嘛，直到買(mǎi)夠?yàn)橹埂?br /> 拿這道題來(lái)講：
1、先做價(jià)格的排序（同時(shí)仍要將牛奶量與之對(duì)應(yīng)）

3 10
5 20
6 30
8 80
9 40

10+20+30+40=100 也就是買(mǎi)到第四行的時(shí)候不必將80個(gè)全買(mǎi)下來(lái)，買(mǎi)40個(gè)就夠了

因此價(jià)格就等于10 * 3 + 20 * 5 + 30 * 6 + 40 * 8 = 630

---

排序

排序難點(diǎn)其實(shí)不在于排價(jià)格，價(jià)格從低到高排列，冒泡啊、插入啊、快排啊、都能解決，難點(diǎn)在于如何將價(jià)格排序的同時(shí)，將對(duì)應(yīng)農(nóng)場(chǎng)的牛奶量也進(jìn)行相應(yīng)的排序（因?yàn)椴捎玫氖莾蓚€(gè)數(shù)組分別存價(jià)格和牛奶量），但仔細(xì)一想，也不難。排價(jià)格數(shù)組的時(shí)候順便把牛奶量數(shù)組的下標(biāo)一改就行了。代碼如下：

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;}} }

---

處理

接下來(lái)就是簡(jiǎn)簡(jiǎn)單單的做小學(xué)數(shù)學(xué)題了。代碼如下：

int deal(int N,int* P,int* A) {mon=0;//價(jià)格重置for (int i = 0; i < M; i++) {int tmp = N < A[i]? N : A[i];//通過(guò)三目運(yùn)算來(lái)?yè)袢∈Ｓ嘈枨蠛娃r(nóng)場(chǎng)i牛奶量之間的最小值mon += tmp * P[i];//計(jì)算價(jià)格N -= tmp;//重新處理剩余需求}return mon;//最終返回所求的最低價(jià)格 }

---

完整代碼

#include <iostream> #include <vector> using namespace std;int N,M;//N需求量，M農(nóng)場(chǎng)數(shù) #define num 5003 int P[num]; int A[num];//P牛奶單價(jià)，A最大供應(yīng)量 int mon;//最低價(jià)格int deal(int N,int* P,int* A) {mon=0;//價(jià)格重置for (int i = 0; i < M; i++) {int tmp = N < A[i]? N : A[i];//通過(guò)三目運(yùn)算來(lái)?yè)袢∈Ｓ嘈枨蠛娃r(nóng)場(chǎng)i牛奶量之間的最小值mon += tmp * P[i];//計(jì)算價(jià)格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++代碼實(shí)現(xiàn)

思路都一樣，只是存儲(chǔ)價(jià)格和牛奶量的方法不再局限于數(shù)組，可以使用容器vector和結(jié)構(gòu)模板pair，以及不用自己實(shí)現(xiàn)sort函數(shù)，可以直接調(diào)用algorithm里的sort函數(shù)。（ps：當(dāng)然c語(yǔ)言也有qsort函數(shù)，但是STL是真的香啊~）

---

排序

寫(xiě)一個(gè)compare函數(shù)的目的主要是為了便于自己理解sort函數(shù)的第三個(gè)參數(shù)，當(dāng)然不寫(xiě)自定義函數(shù)直接將sort的第三個(gè)參數(shù)寫(xiě)成lambda表達(dá)式會(huì)更方便（也更難理解嚶嚶嚶）。哦此處提醒一下，從數(shù)學(xué)上來(lái)看，sort函數(shù)是一個(gè)左邊閉區(qū)間，右邊開(kāi)區(qū)間的域，也就是如果有一個(gè)數(shù)組a[3]，用戶(hù)想要給整個(gè)數(shù)組升序排序要寫(xiě)成sort(a,a+3)，眾所周知a[3]是a+2，當(dāng)然用容器就不牽扯這個(gè)問(wèn)題了。

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農(nóng)場(chǎng)數(shù) int mon;//最低價(jià)格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存儲(chǔ)牛奶單價(jià)(first)和最大供應(yīng)量(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長(zhǎng)什么樣呢？我明天就學(xué)lambda表達(dá)式好叭！

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

總結(jié)

以上是生活随笔為你收集整理的一道很简单的贪心算法题~【贪心：我不要脸的伐？】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。