K12447 采购牛奶

题目描述

周末小科兴高采烈地来到他叔叔的乳制品公司参观，而他的叔叔闷闷不乐，一副很忧愁的样子。原来是因为公司的利润很低，他的叔叔准备降低原材料(牛奶)的价格，公司有很多的牛奶的供应商，要找到最优的牛奶采购方案才能最大力度的降低成本。

公司从很多供应商那里采购牛奶，并且每一个供应商的价格是不同的，每个供应商每天的供应量是一定的，每天公司可以从供应商那里采购到小于或者等于这个供应商能够提供的最大整数数量的牛奶。现在已经知道了公司每天需要采购的牛奶的需求量，以及每个供应商提供的牛奶的单价和供应量。

若要采购足够数量的牛奶，如何采购才能使得花费最小呢。请你帮助小科的叔叔来解决这个问题吧。

输入格式

第一行，两个整数N和M，N表示公司每天需要采购牛奶的需求量；M是提供牛奶的供应商的个数。

接下来M行，每行两个整数pi和ai。pi表示第i个供应商的牛奶的单价，ai表示第i个供应商每天最大供应量。（每天所有供应商的供应量的总和不少于每日公司的需求量）

输出格式

输出一行，一个整数表示公司采购每日需求量的牛奶的最小花费。

输入输出样例

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

输入样例1：

输出样例1：

630

说明

【样例说明】

公司每日所需的牛奶量是100个单位，一共有5个供应商。

从单价为3的供应商那里购买了10个单位的牛奶，花费30元

从单价为5的供应商那里购买了20个单位的牛奶，花费了100元

从单价为6的供应商那里购买了30个单位的牛奶，花费了180元

从单价为8的供应商那里购买了40个单位的牛奶，花费了320元

这样买够100单位的牛奶，总的花费是30+100+180+320=630元

【数据范围】

0≤N≤2*10^6，0≤M≤5000，0≤pi≤1000，0≤ai≤2*10^6

【耗时限制】1000ms 【内存限制】128MB

//
//Created by Carlgood.
//
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct node
{int p,a;
}b[100010];
bool cmp(const node &a,const node &b){return a.p>n>>m;for(int i=1;i<=m;i++){cin>>b[i].p>>b[i].a;}sort(b+1,b+m+1,cmp);int index=1,sum=0;while(n){if(b[index].a!=0){b[index].a--;sum+=b[index].p;n--;}else index++;}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！