首页 > 代码库 > K - 贪心 基础

K - 贪心 基础

2024-09-15 04:38:38   214人阅读

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. 
The warehouse has N rooms. The i-th room contains Jii pounds of JavaBeans and requires Fii pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get Jii* a% pounds of JavaBeans if he pays Fii* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain. 

InputThe 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 Jii and Fii respectively. The last test case is followed by two -1‘s. All integers are not greater than 1000. 
OutputFor each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain. 
Sample Input

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

Sample Output

13.333
31.500

#include<iostream>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<fstream>
#include<memory>
#include<string>
using namespace std;
typedef long long LL;
#define MAXN 1004
#define INF 1000000009
/*
已知每个选择的 收益和花费  而且每个选择不一定要完成全部，收益和花费成比例匹配 求最大收益
贪心算法 不断采用收益比例最大的
*/
int m, n;
struct node
{
    double rate, profit, cost;
}a[MAXN];
bool cmp(node a, node b)
{
    return a.rate > b.rate;
}
int main()
{
    while (scanf("%d%d", &m, &n))
    {
        if (m == -1 && n == -1)
            break;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i].profit >> a[i].cost;
            a[i].rate = a[i].profit / a[i].cost;
        }
        sort(a, a + n, cmp);
        double ans = 0.0, tmp = m;
        for (int i = 0; i < n; i++)
        {
            if (tmp >= a[i].cost)
            {
                ans += a[i].profit;
                tmp -= a[i].cost;
            }
            else
            {
                ans += tmp*a[i].rate;
                break;
            }
        }
        printf("%.3lf\n", ans);
    }
}

 

K - 贪心 基础


联系
我们