Luogu P1016 旅行家的预算

gate

再次感叹我太水了..

贪心策略：

设当前加油站为i，

若i能到达的加油站中有油价比i低的加油站j，则在i加刚好能到达j的油，i→j

若没有，则在i把油加满（注意不要超出终点），i→i能到达的加油站中油价最低的一个

因为double写成int$debug$快一周...

代码如下qaq

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define MogeKo qwq
using namespace std;

const int maxn = 1005;
const int INF = 0x3f3f3f3f;
int n,u;
double m,c,d,v,sum;

struct node {
    double s,p;
    bool operator < (const node &N) const {
        return s < N.s;
    }
} a[maxn];

int main() {
    scanf("%lf%lf%lf%lf%d",&m,&c,&d,&a[0].p,&n);
    for(int i = 1; i <= n; i++)
        scanf("%lf%lf",&a[i].s,&a[i].p);
    sort(a+1,a+n+1);
    a[n+1].s = m;
    a[n+1].p = INF;
    for(int i = 0; i < n+1;) {
        int k = n+1;
        for(int j = i+1; j <= n; j++) {
            if((a[j].s - a[i].s) > c*d) break;
            if(a[j].p < a[k].p) k = j;
            if(a[j].p < a[i].p) break;
        }
        if((a[k].s - a[i].s) > c*d) {
            printf("No Solution");
            return 0;
        }
        if(a[k].p < a[i].p) {
            sum += a[i].p * ((a[k].s - a[i].s)/d - v);
            v = 0;
        } else {
            double v_now = min(c,(a[n+1].s-a[i].s)/d);
            sum += a[i].p * (v_now-v);
            v = v_now - (a[k].s-a[i].s)/d;
        }
        i = k;
    }
    printf("%.2lf\n",sum);
    return 0;
}

View Code