首页 > USACO题解 > USACO Mixing Milk

USACO Mixing Milk

USACO Mixing Milk简单的贪心问题,按照单价从小到大排序,然后对Farmers的牛奶一个一个的进行收购,知道已经买到了所有Milk。代码如下:

/*
	ID:stackex1
	LANG:C
	PROG:milk
*/
#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 5010

typedef struct TagNode
{
	int price;
	int amount;
}Node;
Node node[MAX_NUM];

int cmp(const void *pa, const void *pb)
{
	Node *a = (Node *)pa;
	Node *b = (Node *)pb;
	return a->price > b->price ? 1 : -1;
}

int main(int argc, char **argv)
{
	FILE *fin = fopen("milk.in", "r");
	FILE *fout = fopen("milk.out", "w");
	
	int require, n, i, res;
	fscanf(fin, "%d %d", &require, &n);
	for(i = 0; i < n; ++i)
	{
		fscanf(fin, "%d %d", &node[i].price, &node[i].amount);
	}
	qsort(node, n, sizeof(node[0]), cmp);
	i = res = 0;
	while(require > 0)
	{
		if(require >= node[i].amount)
		{
			require -= node[i].amount;
			res += node[i].price * node[i].amount;
		}
		else 
		{
			res += node[i].price * require;
			require = 0;
		}
		++i;
	}
	fprintf(fout, "%d\n", res);
	
	fclose(fin);
	fclose(fout);
	
	return 0;
}


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> USACO Mixing Milk
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 本文目前尚无任何评论.