C语言贪心算法之贪婪的老鼠

忘是亡心i 2022-06-02 07:24 207阅读 0赞

## Greedy Mouse ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 3

描述

A fat mouse prepared M pounds of cat food,ready to trade with the cats guarding the warehouse containing his

favorite food:peanut. The warehouse has N rooms.The ith room containsW\[i\] pounds of peanut and requires

F\[i\] pounds of cat food. Fatmouse does not have to trade for all the peanut in the room,instead,he may get

W\[i\]\*a% pounds of peanut if he pays F\[i\]\*a% pounds of cat food.The mouse is a stupid mouse,so can you tell

him the maximum amount of peanut he can obtain.

输入

The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers W\[i\] and F\[i\] respectively. The test case is terminated by two -1. All integers are not greater than 1000.

输出

For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of penaut that FatMouse can obtain.

样例输入

5 3
    7 2
    4 3
    5 2
    20 3
    25 18
    24 15
    15 10
    -1 -1

样例输出

13.333
    31.500

上传者

[TC\_李远航][TC]

A的第100道题，挺简单的一道题，原本想第100道题做个难点的，谁知道这道题的难度没有3 ![哭][cry.gif]

#include<stdio.h>
    #include<math.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int cmp(double a,double b)
    {
        return a>b;
    }
    int main()
    {
        int m,n,w[1111],f[1111];
        while(scanf("%d%d",&m,&n)!=EOF)
        {
            if(m==-1&&n==-1)
                break;
            int i,j,t1,t2;
            double ans=0,sum=0,a[1111];
            for(i=0; i<n; i++)
            {
                scanf("%d%d",&w[i],&f[i]);
                a[i]=(double)w[i]/f[i];
            }
            for(i=0; i<n-1; i++)
                for(j=0; j<n-1-i; j++)
                    if(a[j]<a[j+1])
                    {
                        ans=a[j],t1=w[j],t2=f[j];
                        a[j]=a[j+1],w[j]=w[j+1],f[j]=f[j+1];
                        a[j+1]=ans,w[j+1]=t1,f[j+1]=t2;
                    }
            for(i=0; i<n; i++)
            {
                if(m>f[i])
                {
                    sum+=w[i];
                    m=m-f[i];
                }
                else
                {
                    sum+=(double)m*w[i]/f[i];
                    break;
                }
            }
            printf("%.3lf\n",sum);
        }
        return 0;
    }

[TC]: http://59.69.128.203/JudgeOnline/profile.php?userid=TC_%E6%9D%8E%E8%BF%9C%E8%88%AA
[cry.gif]: /images/20220602/ef772795c5da40d89b8e9c402f6ce992.png