1.4.1 USACO Mixing Milk （贪心，sort导致RE）

红太狼 2023-07-17 06:21 11阅读 0赞

# Mixing Milk #

The Merry Milk Makers company buys milk from farmers, packages it into attractive 1- and 2-Unit bottles, and then sells that milk to grocery stores so we can each start our day with delicious cereal and milk.

Since milk packaging is such a difficult business in which to make money, it is important to keep the costs as low as possible. Help Merry Milk Makers purchase the farmers' milk in the cheapest possible manner. The MMM company has an extraordinarily talented marketing department and knows precisely how much milk they need each day to package for their customers.

The company has contracts with several farmers from whom they may purchase milk, and each farmer has a (potentially) different price at which they sell milk to the packing plant. Of course, a herd of cows can only produce so much milk each day, so the farmers already know how much milk they will have available.

Each day, Merry Milk Makers can purchase an integer number of units of milk from each farmer, a number that is always less than or equal to the farmer's limit (and might be the entire production from that farmer, none of the production, or any integer in between).

Given:

*  The Merry Milk Makers' daily requirement of milk
 *  The cost per unit for milk from each farmer
 *  The amount of milk available from each farmer

calculate the minimum amount of money that Merry Milk Makers must spend to meet their daily need for milk.

Note: The total milk produced per day by the farmers will always be sufficient to meet the demands of the Merry Milk Makers even if the prices are high.

### PROGRAM NAME: milk ###

### INPUT FORMAT ###

<table> 
 <tbody> 
  <tr> 
   <td>Line 1:</td> 
   <td>Two integers, N and M.&nbsp;<br> The first value, N, (0 &lt;= N &lt;= 2,000,000) is the amount of milk that Merry Milk Makers wants per day.&nbsp;<br> The second, M, (0 &lt;= M &lt;= 5,000) is the number of farmers that they may buy from.&nbsp;</td> 
  </tr> 
  <tr> 
   <td>Lines 2 through M+1:</td> 
   <td>The next M lines each contain two integers: Pi&nbsp;and Ai.&nbsp;<br> Pi&nbsp;(0 &lt;= Pi&nbsp;&lt;= 1,000) is price in cents that farmer i charges.<br> Ai&nbsp;(0 &lt;= Ai &lt;= 2,000,000) is the amount of milk that farmer i can sell to Merry Milk Makers per day.</td> 
  </tr> 
 </tbody> 
</table>

### SAMPLE INPUT (file milk.in) ###

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

### INPUT EXPLANATION ###

100 5 -- MMM wants 100 units of milk from 5 farmers  
5 20 -- Farmer 1 says, "I can sell you 20 units at 5 cents per unit"  
9 40 etc.  
3 10 -- Farmer 3 says, "I can sell you 10 units at 3 cents per unit"  
8 80 etc.  
6 30 -- Farmer 5 says, "I can sell you 30 units at 6 cents per unit"

### OUTPUT FORMAT ###

A single line with a single integer that is the minimum cost that Merry Milk Makers must pay for one day's milk.

### SAMPLE OUTPUT (file milk.out) ###

630

### OUTPUT EXPLANATION ###

Here's how the MMM company spent only 630 cents to purchase 100 units of milk:

<table> 
 <tbody> 
  <tr> 
   <th>Price<br> per unit</th> 
   <th>Units<br> available</th> 
   <th>Units<br> bought</th> 
   <th>Price *<br> # units</th> 
   <th>Total cost</th> 
   <th>Notes</th> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>20</td> 
   <td>20</td> 
   <td>5*20</td> 
   <td>100</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>40</td> 
   <td>0</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>Bought no milk from farmer 2</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>10</td> 
   <td>10</td> 
   <td>3*10</td> 
   <td>30</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>80</td> 
   <td>40</td> 
   <td>8*40</td> 
   <td>320</td> 
   <td>Did not buy all 80 units!</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>30</td> 
   <td>30</td> 
   <td>6*30</td> 
   <td>180</td> 
  </tr> 
  <tr> 
   <td><strong>Total</strong></td> 
   <td>180</td> 
   <td><strong>100</strong></td> 
   <td>&nbsp;</td> 
   <td><strong>630</strong></td> 
   <td>Cheapest total cost</td> 
  </tr> 
 </tbody> 
</table>

翻译：[https://www.luogu.com.cn/problem/P1208][https_www.luogu.com.cn_problem_P1208]

## 题目描述 ##

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

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

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

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

## 输入格式 ##

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

接下来 mm 行，每行两个整数 p\_i,a\_ipi,ai，表示第 ii 个农民牛奶的单价，和农民 ii 一天最多能卖出的牛奶量。

## 输出格式 ##

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

## 输入输出样例 ##

**输入 \#1**复制

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

**输出 \#1**复制

630

## 说明/提示 ##

【数据范围】  
对于 100\\%100% 的数据：  
0 \\le n,a\_i \\le 2 \\times 10^60≤n,ai≤2×106，0\\le m \\le 50000≤m≤5000，0 \\le p\_i \\le 10000≤pi≤1000

题目翻译来自 NOCOW。

USACO Training Section 1.3

> 题解：（贪心策略）每次都选择单价低的。这里需要注意，使用sort排序时，不能用<=。[https://blog.csdn.net/qq\_29883591/article/details/69063253][https_blog.csdn.net_qq_29883591_article_details_69063253]

/*
    ID: L
    PROG: milk
    LANG: C++ 
    */ 
    #include<bits/stdc++.h> 
    using namespace std;
    using namespace std;
    struct data{
    	int p,q;
    }a[5005];
    bool cmp(data x, data y)//按照单价从低到高排序 
    {
    	return x.p < y.p;//不能用<= ,否则会RE 
    }
    int main()
    {
    	freopen("milk.in","r",stdin);
    	freopen("milk.out","w",stdout);
    	int n,m;
    	scanf("%d%d",&n,&m); 
    	for(int i = 1; i <= m; ++i)
    	{
    		scanf("%d%d",&a[i].p,&a[i].q);
    	}
    	sort(a+1,a+1+m,cmp);
    	int i = 1;
    	long long sum = 0;//总成本 
    	while(n)
    	{
    		if(n > a[i].q)//如果第i个农民的牛奶够需要买的牛奶量 
    		{
    			n = n - a[i].q;//还需要买的牛奶量 
    			sum += a[i].q*a[i].p; 
    		}
    		else 
    		{
    			sum += n*a[i].p;
    			break;
    		}
    		i++;
    	}
    	printf("%d\n",sum);
    	fclose(stdin);
    	fclose(stdout);
    	return 0;
    }

[https_www.luogu.com.cn_problem_P1208]: https://www.luogu.com.cn/problem/P1208
[https_blog.csdn.net_qq_29883591_article_details_69063253]: https://blog.csdn.net/qq_29883591/article/details/69063253