洛谷 P1016 旅行者的预算

传送门

感觉自己连点生活常识都没有，竟然连油用过之后要减去都不知道，这种贪心模拟题都做不出来……思路在代码里，我菜死了

思路&&代码

//看题解过的。。一点都没有成就感
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

inline int read() {//快读
    char c = getchar();
    int x = 0, f = 1;
    for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    return x * f;
}

const int N = 11;

double d1, d2, c, P, ans;//如题目所说
double now, minn = 1000, you;
//now是当前位置，you是指邮箱里还有多少油，minn用来找小于当前p的p
int n, sjp;
//sjp是当前所在加油站的编号

struct node {//结构体存位置
    double d, p;
    bool operator < (const node &b) const {
        return d < b.d;
    }
} e[N];

int main() {
    scanf("%lf%lf%lf%lf", &d1, &c, &d2, &P);
    n = read();
    e[0].d = 0, e[0].p = P;//按要求读入
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &e[i].d, &e[i].p);
    stable_sort(e, e + 1 + n);//排序保险
    double x = c * d2;//加满油走的最远路程
    for(int i = 1; i <= n; i++)
        if(e[i].d - e[i - 1].d > x) return cout << "No Solution", 0;
        //如果两加油站之间的距离大于最远路程，则无解
    while(d1 - now) {//d1是总路程，如果d1-now等于0则走到了终点
        for(int i = sjp + 1; e[i].d - now <= x &&i <= n; i++) {
            if(e[i].p < minn) {//找有没有在最远路程范围内的p小于P的
                minn = e[i].p;//如果有就更新，顺便sjp=i
                sjp = i;
            }
        }
        if(minn <= P) {
            //找到了最远路程范围内比自己的价钱还便宜的
            //就让在目前点加的油刚好能够到这个加油站
            ans += ((e[sjp].d - now) / d2 - you) * P;
            you = (e[sjp].d - now) / d2;//更新油量
        }
        else if(d1 - now <= x) {
            //如果没找到，但d1-now小于x
            //说明可以一次到终点，直接到终点并break
            ans += ((d1 - now) / d2 - you) * P;
            break;
        }
        else {
            //否则就加满油，一直走
            //因为在最大范围内也不能走到比当前加油站价钱低的加油站
            ans += (c - you) * P;
            you = c;//更新油量
        }
        you = you - (e[sjp].d - now) / d2;//用多少减多少
        now = e[sjp].d;//更新当前位置
        P = minn;//更新目前的单价
        minn = 1000;//还原minn，以便下次搜索
    }
    printf("%.2lf", ans);
    return 0;
}