学步园

描述

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

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

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

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

[编辑]格式

PROGRAM NAME: milk

INPUT FORMAT:file milk.in

第 1 行共二个数值:N,(0<=N<=2,000,000)是需要牛奶的总数；M,(0<= M<=5,000)是提供牛奶的农民个数。

第 2 到 M+1 行:每行二个整数:P_i 和 A_i。

P_i(0<= P_i<=1,000) 是农民 i 的牛奶的单价。

A_i(0 <= A_i <= 2,000,000)是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。

OUTPUT FORMAT:file milk.out

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

[编辑]SAMPLE
INPUT

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

[编辑]SAMPLE
OUTPUT

630

解题思路：

简单的贪心算法

将所有的牛奶按价格升序排列（用快排），然后从低到高买入，直到买够m为止。

贪心的证明：

假设某次买了价格稍高的牛奶，可以得到最优解。那么把这次买的牛奶换成价格更低的牛奶，其它不变，那么所得的解较优。假设不成立。

利用桶排的思想可以把代码压缩到极限!参见代码三!

因其价格范围为[0..1000]可以用计数排序来做，就可以得到一个傻瓜代码(参见代码四)。

最佳解题方法：

因为价格的范围在1..1000之内，所以，我们只要在读入数据的时候把相同价格的合并即可，进行计算时，也只需要for i:=0 to 1000 do进行扫描如果有价格为i的牛奶就收购即可，所以不需要排序。

代码：

/*
ID: wikioi_bai
PROG: milk
LANG: C++
*/


# include<cstdio>
# include<iostream>
# include<algorithm>

using namespace std;

# define MAX 5010

struct node
{
    int x;//存放单价
    int y;//存放数量
}a[MAX];

int cmp ( struct node A,struct node B )
    {
        return A.x<B.x;
    }



int main(void)
{
    freopen("milk.in","r",stdin);
    freopen("milk.out","w",stdout);
    int T;
    int n;
    cin>>T>>n;
    int ans = 0;//最小花费
    int sum = 0;//目前奶的量
    for ( int i = 0;i < n;i++ )
        {
           cin>>a[i].x>>a[i].y;
        }
        sort(a,a+n,cmp);
        int k = 0;
        int flag = 1;

    for ( int i = 0;;i++ )
        {
            sum+=a[i].y;
            ans+=(a[i].x) * (a[i].y);

            if ( sum == T )
                {
                    break;
                }
                if ( sum > T )
                    {
                        flag = 0;
                        int cha = sum-T;
                        ans-=(a[i].x) * cha;
                        break;
                    }

        }
            cout<<ans<<endl;







    return 0;
}

桶排的代码：

#include<stdio.h>
int main(){
    freopen("milk.in","r",stdin);
    freopen("milk.out","w",stdout);
    int i,n,m,milk[1100],p,a,fy=0;
    memset(milk,0,sizeof(milk));
    scanf("%d %d",&n,&m);
    for(i=0;i<m;i++){
       scanf("%d %d",&p,&a);
       milk[p]+=a;        
    }
    for(i=0;i<=1000;i++){               
        if(n>milk[i]){
            n-=milk[i];
            fy+=i*milk[i];
        }else{
            fy+=i*n;
            break;  
        }                    
    }
    printf("%d\n",fy);
    return 0;
    }