题解 P1208 【[USACO1.3]混合牛奶 Mixing Milk】

其实根本没有一楼dalao描述的那么麻烦......

一楼dalao其实吧，采用了一种纯属模拟的方式。

下面是我的大跃进思想

但是一个个地做减法是不是太慢了？(大跃进思想)

于是我们是不是可以直接进行一个大跨步式的方法

你的奶我直接全都要了？

敲一个伪代码理解一下

while (当前需要奶量)

{

    if (奶农的提供量<=现在的需求量)

    {

        现在的需求量-奶农的提供量

        你的money-奶农的提供量*奶农的单价

        换一个奶农//这个的提供量已经=0

    }

    else

    {

        你的money-剩余需求量*奶农的单价

        需求量=0

    }

}

然后这个算法的优势就是大跃进

让一个奶农不用分批次给你送牛奶（n--）

直接一步到位，多快好省

然后贴上高清打码的代码

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long int lli;

lli n,m,sum;

struct nainong{

	lli dj,num;

	void input(){cin>>this->dj>>this->num;}

}milk[5001],*now=&milk[1];

bool cmp(const nainong &a,const nainong &b)

{

	if (a.dj!=b.dj)return a.dj<b.dj;

	else return a.num>b.num;

}

int main()

{

	cin>>n>>m;

	for (register int i=1;i<=m;i++)

	{

		milk[i].input();

	}

	sort(milk+1,milk+m+1,cmp);

	while (n)//当任务还没有完成的时候

	{

	    if (now->num<=n)//如果这个奶农产出的奶不够用

	    {

	        n-=now->num;//减掉这个奶农的产量(我全都要了qwq)

	        sum+=(now->dj)*(now->num);//加上这个奶农的要价

	        now++;//移动到下一个位置(or——奶农qwq)

	    }

	    else//奶农产出的奶量不足(任务即将完成)

	    {

	        sum+=(now->dj)*n;//买到最后的奶

	        n=0;//任务完成

	    }

	}

	cout<<sum;

	return 0;

}

然后呢，看看两个代码之间的差距：

(十分建议@chen_zhe 数据加强卡一下，逃qwq)

巴特西

题解 P1208 【[USACO1.3]混合牛奶 Mixing Milk】

一楼dalao其实吧，采用了一种纯属模拟的方式。

下面是我的大跃进思想

你的奶我直接全都要了？

最新文章

热门文章