题目为FatMouse'trade 的一个简单贪心题,测试数据都是对的,但是为什么一直ac不了?麻烦大神们看看啊~~
#include <stdio.h>#include <stdlib.h>
int cmp(const void* a, const void* b);
typedef struct room
{
int bean;
int all_cost;
double average_cost;
};
int main()
{
int catfood = 0 ,room_number = 0;
struct room rooms[1000];
double sum = 0.0;
while (1)
{
sum = 0.0;
scanf("%d%d", &catfood, &room_number);
if (catfood == -1 && room_number == -1)
break;
for (int i = 0; i < room_number; i++)
{
scanf("%d%d", &rooms[i].bean, &rooms[i].all_cost);
rooms[i].average_cost = 1.0 * rooms[i].all_cost / rooms[i].bean;
}
qsort(rooms, room_number, sizeof(struct room), cmp);
for (int i = 0; i < room_number; i++)
{
if (catfood >= rooms[i].all_cost)
{
catfood -= rooms[i].all_cost;
sum += rooms[i].bean;
}
else
{
sum += (1.0 * catfood / rooms[i].all_cost) * rooms[i].bean;
break;
}
}
printf("%.3f\n", sum);
}
return 0;
}
int cmp(const void* a, const void* b)
{
struct room A = *(struct room*)a;
struct room B = *(struct room*)b;
return A.average_cost - B.average_cost > 0.001;
}