题解：P1016 [NOIP 1999 普及组/提高组] 旅行家的预算

Sunrise_up · 2026-05-13 19:55:10 · 题解

求点赞 qwq！

竟然还有远古题可以写题解。

思路

考虑贪心，能加低价油绝不多加高价油。

设第 0 个城市是出发点，第 n+1 个城市是终点。

显然往后走是不优的。

首先按照距离排个序。

假设我们在第 i 个城市，我们可以计算出这一次可以到达的最远的城市 r。那么我们在这么多城市中应该这样选择：

• 可达范围内有比当前更便宜的加油站，即存在 x\in[i+1,r] 且 p_x<p_i，显然选择最近的 x，加最小的油去最近的 x，这样可以避免使用多的高价油（在城市 i 加油）。如果有多个同样最近的城市，那么肯定选择价格最小的。
• 若没有，则选择范围内加油单价最小的城市，在城市 i 加满油再走，这样可以避免使用多的高价油。
• 若没有城市，即 i=r，那么 No solution。

要注意以下几点：

• 终点距离起点为 0 的时候，即 s=0 的时候，要特判，因为我们默认是不在同一个位置停留的。
• 浮点数精度。

代码

时间复杂度 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
struct node{double d,p;}a[10];
const double EPS=1e-6;
double s,c,l,ans,nowg;
int n;
bool cmp(node x,node y){return x.d==y.d?x.p<y.p:x.d<y.d;}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>s>>c>>l>>a[0].p>>n,a[0].d=0;
    if(s<1e-6){cout<<"0.00";return 0;}
    for(int i=1;i<=n;i++)cin>>a[i].d>>a[i].p;
    sort(a,a+n+1,cmp);
    a[n+1].d=s,a[n+2].p=1e9;
    int pos=0;
    while(pos!=n+1){
        int r=pos;
        while(r<=n&&a[r+1].d-a[pos].d<=c*l+EPS)r++;
        if(r==pos){cout<<"No Solution";return 0;}
        int mip=n+2;
        for(int i=pos+1;i<=r;i++){
            if(a[i].p<a[pos].p){mip=i;break;}
            if(a[i].p<a[mip].p)mip=i;
        }
        double nd=(a[mip].d-a[pos].d)/l;
        if(a[mip].p>a[pos].p+EPS)ans+=(c-nowg)*a[pos].p,nowg=c;
        else if(nowg<nd+EPS)ans+=(nd-nowg)*a[pos].p,nowg=nd;
        nowg-=nd,pos=mip;
    }
    printf("%.2f",ans);
}