首页 > 代码库 > P1016 旅行家的预算

P1016 旅行家的预算

提高组贪心傻逼题。

不知道洛谷上的题解是怎么写的。

看BABA我的思路:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define il inline
using namespace std;
il int gi()
{
    int x=0,y=1;
    char ch=getchar();
    while(ch<0||ch>9)
    {
        if(ch==-)
        y=-1;
        ch=getchar();
    }
    while(ch>=0&&ch<=9)
    {
        x=x*10+ch-0;
        ch=getchar();
    }
    return x*y;
}
struct zhan
{
    double dist,pri;
}z[100045];
double mon[100045];//在每个加油站最便宜多少钱的油 
int main()
{
    double all,take,d,p,ans=0,lon;
    scanf("%lf%lf%lf%lf",&all,&take,&d,&p);
    lon=take*d;//每次该加油站最远可以到多远 
    int n;
    cin>>n;
    n++;//把起点加入加油站 
    z[1].dist=0;
    z[1].pri=p;
    for(int i=2;i<=n;i++)
        scanf("%lf%lf",&z[i].dist,&z[i].pri);
    n++;
    z[n].dist=all;
    for(int i=1;i<=n;i++)
    mon[i]=2e8;//赋初值 
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(lon+z[i].dist>=z[j].dist)
            {
                if(z[i].pri<mon[j])//从每个加油站往后看他能影响的加油站,如果更便宜就更新 
                mon[j]=z[i].pri;
            }
            else
            break;
        }
    }
    for(int i=2;i<=n;i++)
    if(mon[i]==2e8)//如果有一个加油站到不了 
    {
        printf("No Solution\n");
        return 0;
    }
    for(int i=2;i<=n;i++)
        ans+=mon[i]*(z[i].dist-z[i-1].dist)/d;//你懂得 
    printf("%.2lf\n",ans);
    return 0;
}

 

P1016 旅行家的预算