老鼠与猫咪做交易，贪心算法，不断选取单价最便宜的购买即可
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000
typedef struct
{
float cm;
int j;
int f;
}JF;
int cmp( const void *a, const void *b)
{
JF *p = (JF *)a;
JF *q = (JF *)b;
if(p -> cm > q -> cm)
return 1;
else
return -1;
}
int main()
{
JF jf[1001];
float left, get;
int N;
int i, j;
scanf("%f%d", & left, & N);
while(N != -1)
{
for(i = 0; i < N; i++)//input && sort
{
scanf("%d%d", &jf[i].j, &jf[i].f);
if(jf[i].j != 0) //j为商品，f为单价。j==0时单价高到无穷
jf[i].cm = 1.0 * jf[i].f / jf[i].j;
else
jf[i].cm = MAX;
}
qsort(jf, N, sizeof(JF), cmp);
get = 0;//init
for(i = 0; i < N && left > 0.0; i++)//trade
{
if(left >= jf[i].f)
{
left -= jf[i].f;
get += jf[i].j;
}
else
{
get += jf[i].j * left / jf[i].f;
left = 0.0;
}
}
printf("%.3f\n", get);//out
scanf("%f%d", & left, & N);
}
}
。
1.需要注意的是边界情况，j的输入是可以为0的，这个时候可以将单价cm=f/j设为无穷大。
2.另外还要注意一些细节，结构体中将j、f设为int，cm为float，因此要将cm=1.0*f/j，否则cm的值会为0。
posted on 2012-02-19 21:56
小鼠标 阅读(256)
评论(0) 编辑 收藏 引用