求助!简单贪心没过,求好心人指导
查看原帖
求助!简单贪心没过,求好心人指导
710787
shaodao楼主2022/10/14 09:41

求助!

自己输入的案例通过了(240.00)但是提交后没一个过

代码整体思路就是在性价比层面进行排序,尽量选性价比高的, 直到背包装满或者物品遍历完

求好心人帮忙指导指导,万分感谢

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110 ,M = 1010;

struct Range
{
    int a , b ;
    double c;
    bool operator < (const Range& w) const
    {
        return c < w.c;
    }
}ranges[M];

int n , m ;

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++ )
    {
        int a , b;
        cin >> a >> b;
        ranges[i] = {a,b,b/a};
    }
    
    sort(ranges + 1 , ranges + 1 + n);
    
    double ans = 0 ;
    int res = n;
    while(m && res)
    {
        int x = min(m , ranges[res].a);
        // 如果装不下则为m , 装得下则为金币体积
        ans+=x * ranges[res].c;
        m-=x;
        res --;
    }

    printf("%.2f" , ans);
    cout << endl;
    return 0;
}
2022/10/14 09:41
加载中...