3TLE
查看原帖
3TLE
355643
蒟蒻QWQ2008楼主2020/7/3 14:45
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
    double d;
    double p;
}s[10];
int cmp(node a,node b)
{
    return a.d<b.d;
}
int main()
{
    double D1,c,D2,cost=0,left=0;
    int n;
    scanf("%lf%lf%lf%lf%d",&D1,&c,&D2,&s[0].p,&n);
    s[n+1].d=D1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&s[i].d,&s[i].p);
        if(s[i].d-s[i-1].d>c*D2)//如果加油站的距离大于油箱容量乘每升行驶距离
        {
            printf("No Solution");//则不能到达
            return 0;//结束
        }
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n+1;)
    {
        int j,k;
        for(j=k=i+1;j<n+1;j++)
        {
            k=s[j].p>=s[k].p?k:j;//范围内找到最便宜的加油站
            if(s[j].p<=s[i].p||s[j+1].d-s[i].d>c*D2)//如果找到比当前加油站便宜的加油站或到不了下一个加油站
            {
                break;
            }
            if(s[j].p>s[i].p)//范围内没有更便宜的
            {
                cost+=(c-left)*s[i].p;
                left=c-(s[k].d-s[i].d)/D2;
                i=k;
            }
            else//范围内没有更便宜的
            {
                cost+=s[i].p*((s[j].d-s[i].d)/D2-left);
                i=j;
                left=0;
            }
        }
    }
    printf("%.2lf",cost);
}

2020/7/3 14:45
加载中...