比赛 贪心题目练习 评测结果 C
题目名称 旅行家的预算 最终得分 0
用户昵称 长安惊龙灵松 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2025-03-22 10:17:11
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
double minn=0x3fffffff,d1,c,d2,d[11],p[11],dm,ans,cn;
int w,wn,n;
int main()
{
    freopen("lyuxing.in","r",stdin);
    freopen("lyuxing.out","w",stdout); 
    scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p[0],&n);
    dm=c*d2;
//    cout<<dm<<endl;
    d[n+1]=d1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&d[i],&p[i]);
        if(d[i]-d[i-1]>dm)
        {
            printf("No Solution");
            return 0;
        }
    }
    if(d[i]-d[i-1]>dm)
    {
        printf("No Solution");
        return 0;
    }
    while(wn!=n+1)
    {
        minn=0x3fffffff;
        for(int i=wn+1;i<=n+1&&d[i]-d[wn]<=dm;i++)
        {
            if(p[i]<=minn)
            {
                w=i;
                minn=p[i];
            }
            if(minn<=p[wn]) 
            {
//                cout<<" "<<minn<<endl;
                break;
            }
        }
        ans+=(d[w]-d[wn])/d2*p[wn];
        wn=w;
        
//        cout<<wn<<endl;
    }
    printf("%.2lf",ans);
    return 0;  
}