老鼠與貓咪做交易，貪心算法，不斷選取單價最便宜的購買即可
#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
小鼠標 閱讀(274)
評論(0) 編輯 收藏 引用