1.3.1 Mixing Milk 混合牛奶

code

4 年前

时间： 1ms 内存：64M

描述：

牛奶包装是一个如此低利润的生意,以至于尽可能低地控制初级产品(牛奶)的价格变得十分重要。请帮助Merry的牛奶制造公司(Merry Milk Makers')以尽可能最廉价的方式取得他们所需的牛奶。Merry的牛奶制造公司从一些农民那购买牛奶，每个农民卖给牛奶制造公司的价格不一定相同。而且,如一只母牛一天只能生产一定量的牛奶,农民每一天只有一定量的牛奶可以卖。每天,Merry的牛奶制造公司从每个农民那购买一定量的牛奶,少于或等于农民所能提供的最大值。给出Merry牛奶制造公司的每日的牛奶需求,连同每个农民的可提供的牛奶量和每加仑的价格,请计算Merry的牛奶制造公司所要付出钱的最小值。

注意:每天农民生产的牛奶的总数对Merry的牛奶制造公司来说是足够的

输入：

第 1 行共二个数值:N,(0<=N<=2,000,000)是需要牛奶的总数；M,(0<= M<=5,000)是提供牛奶的农民个数。第 2 到 M+1 行:每行二个整数:Pi 和 Ai。 Pi(0<= Pi<=1,000) 是农民 i 的牛奶的价格。 Ai(0 <= Ai <= 2,000,000)是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。

输出：

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

示例输入：

示例输出：

提示：

参考答案（内存最优[748]）：

#include<stdio.h>
#include<stdlib.h>
#define MAX 5005
typedef struct{
	int p,a;
}milk;
int cmp(const void *a,const void *b)
{
	return (*(milk*)a).p-(*(milk*)b).p;
}
int main()
{
	int n,m;
	while(scanf("%d %d",&n,&m)==2){
		milk p[MAX];
		int i,j,sum=0;
		for(i=1;i<=m;i++)
			scanf("%d %d",&p[i].p,&p[i].a);
		qsort(&p[1],m,sizeof(milk),cmp);
		i=1;
		while(n&&i<=m){
			if(n>=p[i].a){
				sum+=p[i].a*p[i].p;
				n-=p[i].a;
			}
			else{
				sum+=p[i].p*n;
				n-=n;
			}
			i++;
		}
		printf("%d\n",sum);
	}
	return 0;
}

参考答案（时间最优[4]）：

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
struct ab
{
    int money;
    long int num;
}d[5000];
bool cmp(ab a, ab b)
{
    return a.money<b.money;
}
int main()
{
    long int s;
    int n;
    cin>>s>>n;
    for(int i=0;i<n;i++)
        cin>>d[i].money>>d[i].num;
    sort(d,d+n,cmp);
    long int k=0;
    for(int i=0;i<n;i++)
    {
        if(d[i].num>s)
        {
            k+=s*d[i].money;
            s=0;
        }
        else k+=d[i].money*d[i].num,s-=d[i].num;
        if(s==0)break;
    }
    cout<<k<<endl;
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。