题目链接

很经典的一道贪心题,今天在洛谷上刷到了,就再做一遍
竟然是道黄题,赶紧水一下
没想到竟然WA了一次,确实提醒了我一下,写题的时候别手***r> 思路就是一个简单的贪心,按照性价比来排序,因为金币是可以分开的所以拿不完就拿一部分
还有就是其实有除的话尽量推公式换成乘法,除容易有误差但这道题数据太水了 数据的类型转换还是要注意的
以及double的数比较大小的时候别忘了有误差,浮点数相等应该是这种形式:a-b<1e-6 别忘了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e4+7;
const ll mod=2147483647;
struct node
{
    ll m,v;
    double w;//性价比
    bool operator<(const node &a)const//排序
    {
        return w>a.w;
    }
}f[N];
ll n,m,t;
int main()
{
    scanf("%lld %lld",&n,&t);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld %lld",&f[i].m,&f[i].v);
        f[i].w=(double)f[i].v/(double)f[i].m;//注意类型转换
    }
    sort(f+1,f+1+n);
    double sum=0.0;
    ll now=0;
    for(int i=1;i<=n;++i)
    {
        if(f[i].m+now<=t)
        {
            sum+=(double)f[i].v,now+=f[i].m;
            if(now==t)break;
        }
        else {
                sum+=double(t-now)*f[i].w;
                break;
        }
    }
    printf("%.2f\n",sum);//就不该放到里面
    return 0;
}