洛谷P1016 [NOIP1999 提高组] 旅行家的预算 题解

题目链接：P1016 [NOIP1999 提高组] 旅行家的预算

题意：

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 $D_1$、汽车油箱的容量 $C$（以升为单位）、每升汽油能行驶的距离 $D_2$、出发点每升汽油价格$P$和沿途油站数 $N$（$N$ 可以为零），油站 $i$ 离出发点的距离 $D_i$、每升汽油价格 $P_i$（$i=1,2,…,N$）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。

$N \le 6$，其余数字$ \le 500$。

经典的反悔型贪心

每次碰到一个加油站，烧掉最便宜的油（从上一个位置到现在位置）

接着退掉比当前加油站贵的油（反悔），然后直接加满当前加油站的油

记得设一个终点站，显然它和起点的距离为 $d_1$ ，推掉所有多的油

这个油价的维护直接用单调队列维护，这里用deque<node>来搞方便一些

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <deque>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(15)

int n;
double d1,c,d2,p[N],d[N];
struct node{double cost,x;};
deque<node> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> d1 >> c >> d2 >> p[0] >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> d[i] >> p[i];
        if(d[i]-d[i-1]>c*d2)
            return cout << "No Solution\n",0;
    }
    d[n+1]=d1;
    double nc=c,res=0;
    q.push_back({p[0],nc});
    res+=p[0]*c;
    for(int i=1; i<=n+1; i++)
    {
        double nd=(d[i]-d[i-1])/d2;
        while(!q.empty()&&nd>0)
        {
            node u=q.front(); q.pop_front();
            if(u.x>nd)
            {
                nc-=nd;
                q.push_front({u.cost,u.x-nd});
                break;
            }
            nc-=u.x; nd-=u.x;
        }
        if(i==n+1)
        {
            while(!q.empty())
            {
                res-=q.front().cost*q.front().x;
                q.pop_front();
            }
            break;
        }
        while(!q.empty()&&q.back().cost>p[i])
        {
            res-=q.back().cost*q.back().x;
            nc-=q.back().x;
            q.pop_back();
        }
        res+=(c-nc)*p[i];
        q.push_back({p[i],c-nc});
        nc=c;
    }
    cout << fixed << setprecision(2) << res << '\n';
    return 0;
}

参考文献

[1] https://www.luogu.com.cn/blog/hongzy/solution-p1016