FatMouse' Trade

今天重新翻出了HDU的ACM Steps中的题目做了一下，发现一道比较简单的题目。

题目链接: 题目

题目的思路大致可以分为两个部分：

第一部分：将每个房间中JavaBeans和cat food的比例（精确到小数点后三位）分别求出来并存在一个数组之中，并将这个数组进行从大到小的排序。

第二部分：对排序好的数组从大到小，依次累加其对应的JavaBeans的数量直至cat food不足以付出一个房间的cat food要求，再用之前的比例进行计算，统计所得到的所有JavaBeans的数量。

代码如下：

#include <stdio.h>
struct c{
    int j;
int u;
double k;
    };
    void sort(struct c *a, int left, int right)
{
    if(left >= right)
        return;
    int x = left;
    int y = right;
    double key = a[left].k;
    double key1 = a[left].j;
    double key2 = a[left].u;

    while(x<y)
    {
        while(x<y && key <= a[y].k)
        {
            y--;
        }

        a[x].j=a[y].j;
           a[x].u=a[y].u;
        a[x].k=a[y].k;

        while(x<y && key >=a[x].k)
        {
            x++;
        }   

        a[y].j=a[x].j;
        a[y].u=a[x].u;
        a[y].k=a[x].k;
    }

    a[x].j = key1;
    a[x].u = key2;
    a[x].k = key;
    sort(a, left, x - 1);
    sort(a, x+1, right);

}

struct c f[1000];
int main()
{
    int m,n,i;
    int a,b;
    while(scanf("%d %d",&m,&n)!=EOF && m!=-1 && n!=-1)
    {
        double count=0;
        for(i=1;i<=n;i++)
        {
        scanf("%d %d",&a,&b);
        f[i].j=a;
        f[i].u=b;
        f[i].k=(double)a/b;
        }
        sort(f,1,n);
        for(i=n;i>=1;i--)
        {
            if(m >= f[i].u)
                count+=f[i].j;
            else
            {    
                count=count+f[i].k*m;
                break;
            }
            m-=f[i].u;
        }
        printf("%.3f\n", count);
    }
    return 0;
}

仔细想想，应该还有更简便的方法，期待下次能更新～