Skip to content

11252: 【原1252】商家的筹划

题目

题目描述

author: Xingdong Li 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1252 

Description

一家乳制品公司每天需要一定量的牛奶，于是他们需要在诸多奶农中采购牛奶。

每位奶农每天能够提供的牛奶是一定的，乳制品公司可以向他们收购小于或等于最大产奶量的牛奶。

给出公司每天需要的牛奶数量和奶农提供的牛奶最大数量与单价，需要你给出采购足够牛奶需要的最小费用。

Input Format

第一行有两个整数：N，（0<=N<=200000)是需要牛奶的总数；M，（0<=M<=5000)是提供牛奶的奶农个数。

接下来有M行，每行有两个整数：P 与 A。

P(0<=P<=1000)是牛奶的单价。

A(0<=A<=2000000)是奶农能提供的牛奶数量。

Output Format

仅有一行，输出采购足够牛奶需要的最小费用。

Sample Input

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

Sample Output

630

WashSwang's solution 

#include <iostream>
#include <cstdio>
#include <algorithm>
long long s[1001];
int n,m,x,y,ans;
int main() {
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;++i)
    {
        scanf("%d%d",&x,&y);
        s[x]+=y;
    }
    for (int i=0;i<1000;++i)
    {
        if (n>s[i]){
            n-=s[i];
            ans+=s[i]*i;
        }
        else
        {
            ans+=n*i;
            break;
        }
    }
    printf("%d",ans);
    return 0;
}