现在的位置: 首页 > 综合 > 正文

【ACM】杭电1070:Milk

2012年06月12日 ⁄ 综合 ⁄ 共 1256字 ⁄ 字号 评论关闭

思路分析:

先求出每个品牌平均每天的花费,再比较这些平均花费的大小,选择最小的即可。如果平均花费相同,则选择容量大的品牌。可以用一个结构体来储存品牌相关信息:

struct brand
{
	char ch[120];
	int price;
	int v;
	double ave; /* the average cost of one day */
};
typedef struct brand BRAND;

注意:

1、如果一瓶的奶量少于200ml,则应该忽视这个品牌。

2、如果一瓶的奶量高于1000ml(够喝5天的了),则平均花费只需要用单价除以5即可。

3、只买一次奶,最多喝5天。

代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct brand
{
	char ch[120];
	int price;
	int v;
	double ave; /* the average cost of one day */
};
typedef struct brand BRAND;
int compare(const void *a,const void *b) /* high to low order */
{
	BRAND *x = (BRAND*)a;
	BRAND *y = (BRAND*)b;
	if(x->v < y->v)
		return 1;
	else if(x->v == y->v)
		return 0;
	else
		return -1;
}
int find_min(BRAND *bd,int len)
{
	int i,ix_min = 0;
	for(i = 1 ; i < len ; ++i)
	{
		if(bd[i].ave < bd[ix_min].ave)
			ix_min = i;
	}
	return ix_min;
}
double cost(BRAND *b) /* the cost of one day */
{
	return (double)b->price / (b->v / 200);
}
int main(int argc, char *argv[])
{
	int T,t,i,j,n;
	BRAND bd[110];
	scanf("%d",&T);
	for(t = 1 ; t <= T ; ++t) /* T input set */
	{
		memset(bd,0,sizeof(bd));
		scanf("%d",&n); /* amount of the brands */
		for(j = 0 ; j < n ; ++j)
		{
			scanf("%s",bd[j].ch); /* the information of the brand */
			scanf("%d%d",&bd[j].price,&bd[j].v);
			
			if(bd[j].v < 200) /* not enough */
			{
				bd[j].ave = 9999999;
				continue; /* get the next brand */
			}
			if(bd[j].v > 1000)
				bd[j].ave = bd[j].price / (double)5;
			else
				bd[j].ave = cost(&bd[j]);
		}
		qsort(bd,n,sizeof(BRAND),compare);
		printf("%s\n",bd[find_min(bd,n)].ch);
		
	}
	return 0;
}

抱歉!评论已关闭.