2019.7.26
由于乳制品產(chǎn)業(yè)利潤(rùn)很低当悔，所以降低原材料（牛奶）價(jià)格就變得十分重要。幫助Marry乳業(yè)找到最優(yōu)的牛奶采購(gòu)方案却紧。
Marry乳業(yè)從一些奶農(nóng)手中采購(gòu)牛奶陌僵，并且每一位奶農(nóng)為乳制品加工企業(yè)提供的價(jià)格是不同的。此外虐秦，就像每頭奶牛每天只能擠出固定數(shù)量的奶譬猫，每位奶農(nóng)每天能提供的牛奶數(shù)量是一定的。每天Marry乳業(yè)可以從奶農(nóng)手中采購(gòu)到小于或者等于奶農(nóng)最大產(chǎn)量的整數(shù)數(shù)量的牛奶羡疗。
給出Marry乳業(yè)每天對(duì)牛奶的需求量染服，還有每位奶農(nóng)提供的牛奶單價(jià)和產(chǎn)量。計(jì)算采購(gòu)足夠數(shù)量的牛奶所需的最小花費(fèi)叨恨。
注：每天所有奶農(nóng)的總產(chǎn)量大于Marry乳業(yè)的需求量柳刮。
輸入格式
第 1 行共二個(gè)數(shù)值:N,(0<=N<=2,000,000)是需要牛奶的總數(shù)；M,(0<= M<=5,000)是提供牛奶的農(nóng)民個(gè)數(shù)痒钝。
第 2 到 M+1 行:每行二個(gè)整數(shù):Pi 和 Ai秉颗。
Pi(0<= Pi<=1,000) 是農(nóng)民 i 的牛奶的單價(jià)。
Ai(0 <= Ai <= 2,000,000)是農(nóng)民 i 一天能賣給Marry的牛奶制造公司的牛奶數(shù)量送矩。
輸出格式
單獨(dú)的一行包含單獨(dú)的一個(gè)整數(shù)蚕甥，表示Marry的牛奶制造公司拿到所需的牛奶所要的最小費(fèi)用。
輸入輸出樣例
輸入
100 5
5 20
9 40
3 10
8 80
6 30
輸出
630
我的思路：
構(gòu)造一個(gè)結(jié)構(gòu)體來(lái)儲(chǔ)存Pi和Ai栋荸，排序時(shí)將單價(jià)小的放在前面菇怀，如果單價(jià)相同，就把數(shù)量大的放在前面晌块。用一個(gè)while循環(huán)爱沟，條件是n為零時(shí)就停止，每循環(huán)一次i加一匆背，對(duì)應(yīng)下一個(gè)次小單價(jià)呼伸。如果當(dāng)前最小單價(jià)對(duì)應(yīng)的牛奶供應(yīng)量小于n，說(shuō)明此當(dāng)前最小單價(jià)的所有牛奶都會(huì)被收購(gòu)钝尸，n減去當(dāng)前的牛奶供應(yīng)量括享，ans變量用來(lái)存儲(chǔ)所需的錢數(shù)，每次對(duì)ans進(jìn)行相應(yīng)的加操作珍促；當(dāng)然如果當(dāng)前最小單價(jià)對(duì)應(yīng)的牛奶供應(yīng)量大于n铃辖，說(shuō)明當(dāng)前最小單價(jià)的牛奶不能被全部收購(gòu)，只買數(shù)量為n的牛奶就可以踢星，到此澳叉，公司已經(jīng)買到了需要的牛奶量隙咸，n=0，ans加上n*單價(jià)成洗，循環(huán)結(jié)束五督，輸出ans。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
int a;
int b;
}a[50005];
bool cmp(node q, const node w)
{
if(q.a != w.a)
return q.a < w.a;
else
return q.b > w.b;
}
int main()
{
int n, m;
int ans = 0;
cin >> n >> m;
for(int i=0; i<m; i++)
{
cin >> a[i].a >> a[i].b;
}
sort(a,a+m,cmp);
int i=0;
while(n)
{
if(a[i].b < n)
{
n -= a[i].b;
ans += a[i].a * a[i].b;
}
else
{
ans += a[i].a * n;
n = 0;
}
i++;
}
cout << ans << endl;
return 0;
}
