洛谷P4712题解

题解

前置知识：

• C++

题目链接

P4712 「生物」能量流动

解题思路

贪心的思想，要想要获得的能量最多，就要保证流失的能量最少。由题目可知，r_i+1 >=r_i，后面的食量不小于前面的食量，后面的可以吃到后面的生物，前面的只能吃前面的生物，由此可以得到贪心策略：从前往后尽量满足食物。
复杂度据说是O(nlogn),但我不会算……实测跑得很快。

代码

#include<stdio.h>
double a[100005];
int main()
{
    int n,i,left=0,d,j,flag = 0;
    double x,tmp;
    scanf("%d%lf",&n,&a[0]);
    for(i=1; i<=n; i++)
    {
        scanf("%lf%d",&x,&d);
        tmp = x;
        for(j=left; j<=d; j++)
        {
           // printf("%f %f\n",x,a[j]);
           if(a[j]<1e-9) left = j;
            if(x<=a[j]/5.0+1e-10)
            {
                a[j]-=5*x;
                a[i]=tmp;
                x=0;
                break;
            }
            else
            {
                x=x-(a[j]/5.0);
                a[j]=0;
                left++;
            }
        }
        if(x>1e-9)
        {
            printf("-1\n");
            return 0;
        }
    }
    double sum=0;
    for(i=left;i<=n;i++)
    {
        sum+=a[i];
    }
    printf("%f\n",sum/5.0);
}