P1208 [USACO1.3]混合牛奶 Mixing Milk(贪心思想加一点特别的循环)

简介: P1208 [USACO1.3]混合牛奶 Mixing Milk(贪心思想加一点特别的循环)

题目描述



由于乳制品产业利润很低,所以降低原材料(牛奶)价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。


Marry 乳业从一些奶农手中采购牛奶,并且每一位奶农为乳制品加工企业提供的价格是不同的。此外,就像每头奶牛每天只能挤出固定数量的奶,每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。


给出 Marry 乳业每天对牛奶的需求量,还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。


注:每天所有奶农的总产量大于 Marry 乳业的需求量。


输入格式



第一行二个整数 n,m,表示需要牛奶的总量,和提供牛奶的农民个数。

接下来  m 行,每行两个整数 pi,ai,表示第  i 个农民牛奶的单价,和农民 i  一天最多能卖出的牛奶量。


输出格式



单独的一行包含单独的一个整数,表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用。


输入输出样例



输入 #1复制

100 5

5 20

9 40

3 10

8 80

6 30


输出 #1复制

630


说明/提示



【数据范围】

对于  100% 的数据:

0≤n,ai≤2×106, 0≤m≤5000, 0≤pi≤1000

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
struct node{
  int x,y;
}s[maxn];
bool cmp(node a,node b)
{
return a.x<b.x; 
}
int main()
{
  int m,n;int ans=0;
  cin>>m>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>s[i].x>>s[i].y; 
  } 
  sort(s+1,s+1+n,cmp);
  int j=1;
  while(m)
  {
      if(s[j].y)//我们可以一套一套的买完 
      {
        s[j].y--;
        ans+=s[j].x;
        m--;
      }
      else
      j++;
  }
  cout<<ans;
}



目录
打赏
0
0
0
0
8
分享
相关文章
|
9月前
【每日一题Day297】LC1444切披萨的方案数 | 动态规划+二维前缀和
【每日一题Day297】LC1444切披萨的方案数 | 动态规划+二维前缀和
84 0
PTA之N个数求和(细节题)天梯赛
编程题,要求计算以分子/分母形式给出的一组有理数的和,输出结果也要是最简有理数形式。输入包含正整数N(N≤100)及N个有理数,输出为和的最简形式。示例:输入5个数2/5, 4/15, 1/30, -2/60, 8/3,输出3 1/3;输入2个数4/3, 2/3,输出2。代码中包含求最大公约数的函数和计算有理数和的主要逻辑。
76 0
【状态压缩 容斥原理 组合数学】3116. 单面值组合的第 K 小金额
【状态压缩 容斥原理 组合数学】3116. 单面值组合的第 K 小金额
|
9月前
【编程题-错题集】分割等和子集(动态规划 - 01背包)
【编程题-错题集】分割等和子集(动态规划 - 01背包)
UPC - 2022春混合个人训练赛第五场 D Seahorse Shoes(贪心+模拟)
UPC - 2022春混合个人训练赛第五场 D Seahorse Shoes(贪心+模拟)
108 0
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
77 1
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-913 二元函数
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-913 二元函数
49 0
第十四届蓝桥杯集训——练习解题阶段(无序阶段)- 基础练习 序列求和
第十四届蓝桥杯集训——练习解题阶段(无序阶段)- 基础练习 序列求和
52 0
算法提高:组合数学| 卡特兰数的实现
卡特兰数列是组合数学中在各种计数问题中常出现的数列,其前几项为1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012…… 卡特兰数首先是由欧拉在计算对凸n边形的不同的对角三角形剖分的个数问题时得到的,即在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数用Hn表示,Hn即卡特兰数。
164 0
算法提高:组合数学| 卡特兰数的实现