题解 | To Fill or Not to Fill

#include <iostream>//思路错了，借鉴了大佬的思路 贪心排序油费
#include <algorithm>
#include <cmath>
#include <cstring>
#include <limits>
#include <stack>
#define maxn 510
using namespace std;
typedef struct stack{
    double P;//开double精度才够
    double D;
    double maxD;
}Sta;

bool dis[30010];//标记走过的路

bool cmp(Sta s1,Sta s2)
{
    return s1.P<s2.P;
}
int main() {
    int Cmax,D,Davg,N;
    while(cin>>Cmax>>D>>Davg>>N)
    {
        Sta sta[maxn];
        for(int i=0;i<N;i++)
        {
            cin>>sta[i].P>>sta[i].D;
            sta[i].maxD = sta[i].D + (Cmax*Davg*1.0);//计算最远可以走到哪里
            
        }
        sort(sta,sta+N,cmp);//排序
        memset(dis,0,sizeof(dis));
     //   for(int i=0;i<N;i++)cout<<"pri: "<<sta[i].P<<" D : "<<sta[i].D<<" max = "<<sta[i].maxD<<endl;
        double ans=0;
        for(int i = 0;i<N;i++)
        {
            int l,r,cnt=0;
            l = sta[i].D;
            r = sta[i].maxD;
            if(sta[i].D==0)dis[0]=1;
            for(int j=l+1;j<=r&&j<=D;j++)
            {
                if(!dis[j]){
                    dis[j]=1;
                    cnt++;//计算走的路程
                }
            }
   //     cout<<sta[i].P<<" "<<l<<" "<<r<<" cnt ="<<cnt<<endl;
        //    cout<<"cnt = "<<cnt<<endl;
            ans = ans + (cnt *1.0/Davg)* sta[i].P*1.0;//邮费
        }
        int flag = 0;
        double diss;
        for(int i=0;i<=D;i++)
        {
            if(dis[i]==0){
                flag = 1;
                diss = i;
                break;
            }
        }
    //    cout<<1<<" "<<dis[1]<<endl;
        if(flag)printf("The maximum travel distance = %.2lf\n",diss-1);
        else printf("%.2lf\n",ans);

    }
}
// 64 位输出请用 printf("%lld")