CODE[VS] 1621 混合牛奶 USACO

題目描述?Description

牛奶包裝是一個如此低利潤的生意,所以盡可能低的控制初級產品(牛奶)的價格變的十分重要.
請幫助快樂的牛奶制造者(Merry Milk Makers)以可能的最廉價的方式取得他們所需的牛奶.
快樂的牛奶制造公司從一些農民那購買牛奶,每個農民賣給牛奶制造公司的價格不一定相同.
而且,如一只母牛一天只能生產一定量的牛奶,農民每一天只有一定量的牛奶可以賣.
每天,快樂的牛奶制造者從每個農民那購買一定量的牛奶,少于或等于農民所能提供的最大值.
給出快樂牛奶制造者的每日的牛奶需求,連同每個農民的可提供的牛奶量和每加侖的價格,請計算快樂的牛奶制造者所要付出錢的最小值.

注意:
每天農民生產的牛奶的總數對快樂的牛奶制造者來說足夠的.

輸入描述?Input Description

第 1 行:二個整數, N 和 M.
N(0<= N<=2,000,000)是快樂的牛奶制造者的一天需要牛奶的數量.
M(0<= M<=5,000)是農民的數目.

?

第 2 到 M+1 行:每行二個整數,Pi 和 Ai.
Pi(0<= Pi<=1,000) 是農民 i 牛奶的價格.
Ai(0 <= Ai <= 2,000,000)是農民 i 一天能賣給快樂的牛奶制造者的牛奶數量.

輸出描述?Output Description

單獨的一行包含單獨的一個整數,表示快樂的牛奶制造者拿到所需的牛奶所要的最小費用

樣例輸入?Sample Input

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

樣例輸出?Sample Output

630

?

我真厲害，

hh。

?

基礎題，

按價格排序，

價格低者先購買。

?

代碼：

?

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

int n,m;
long long ans,q;

struct node{
    int pr,cou;
}a[5002];

bool cmp(node x,node y)
{
    return x.pr <y.pr ;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d%d",&a[i].pr ,&a[i].cou );
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;++i)
    {
        if(n-q<=a[i].cou )
        {
            ans+=a[i].pr *(n-q);
            break;
        }
        if(q==n) break;
        q+=a[i].cou ;
        ans+=a[i].pr *a[i].cou ;
    }
    printf("%lld",ans);
    return 0;
}

?

---

如果你不開心，那我就把右邊這個帥傻子分享給你吧，

你看，他這么好看，那么深情的望著你，你還傷心嗎？

真的！這照片盯上他五秒鐘就想笑了。

一切都會過去的。

?

?