ACM1009：FatMouse' Trade

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#define SIZE 1001
int J[SIZE];
int F[SIZE];
double rate[SIZE];
int bigger(int a, double keyRate, double keyJ);
int main()
{
	int M, N;
	int i, j, tempIndex;
	double tempRate,tempJ,tempF;
	double total;
	while (scanf("%d%d", &M, &N) == 2)
	{
		total = 0;
		if (M == -1 && N == -1)
			break;
		for (i = 0; i < N; i++)
		{
			scanf("%d%d", &J[i], &F[i]);
			rate[i] = ((double)F[i] / J[i]);
		}
		//插入排序
		for (i = 1; i < N; i++)
		{
			tempRate = rate[i];
			tempJ = J[i];
			tempF = F[i];
			tempIndex = i;
			j = i - 1;
			while (j >= 0 && bigger(j, tempRate, tempJ))
			{
				rate[j + 1] = rate[j];
				J[j + 1] = J[j];
				F[j + 1] = F[j];
				j = j - 1;
			}
			rate[j + 1] = tempRate;
			J[j + 1] = tempJ;
			F[j + 1] = tempF;
		}

		for (i = 0; i < N; i++)
		{
			//判断比率为0，也就是免费送的情况
			if (M > F[i] || rate[i] <= 0.0000001)
			{
				total += J[i];
				M -= F[i];
			}
			else
			{
				total += (double)M / F[i] * J[i];
				break;
			}
		}
		printf("%0.3f\n", total);
	}
}

int bigger(int a, double keyRate, double keyJ)
{
	if (fabs(rate[a] - keyRate) <= 0.000001)
		return J[a] < keyJ;
	else
	{
		return rate[a] > keyRate;
	}
}