「NOIP 1999」旅行家的预算

#贪心

Published on 2016-11-02

描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 $d_1$ 、汽车油箱的容量 $c$ （以升为单位）、每升汽油能行驶的距离 $d_2$ 、出发点每升汽油价格 $p$ 和沿途油站数 $n(n\le 100)$ ，油站 $i$ 离出发点的距离 $d_i$ 、每升汽油价格 $p_i$ 。
输入数据除了 $n$ 均为实数，计算结果四舍五入至小数点后两位。
如果无法到达目的地，则输出 -1。

分析

先判掉无解，如果两个之间的路用 $c$ 的油跑不完，那么就无解。

这个题的容量是实数，没办法做动态规划的状态，所以考虑贪心。
考虑从起点出发（设标号为 $0$ ），我们找到从起点出发满油能达到的 $j$ ，如果 $[1, j]$ 中不存在一个价格比 $0$ 小的点，那么显然是在 $0$ 加满油，一直跑到 $j$ 最优。如果 $[1, j]$ 存在一个价格最小的 $k$ ，满足价格比 $i$ 小，那么我们显然是在 $i$ 处加恰好能走到 $k$ 的油，然后走到 $k$ 。

一直延续这个算法做下去，直到到达终点。注意每一次到一个点可能会有余油，我们应该先用余油。可以使用反证法证明贪心的正确性。
复杂度 $O(n^2)$ ，可以用单调队列做到 $O(n)$ 。

思考：这个题我的第一想法是 DP，用 $f[i][j]$ 表示到 $i$ 点，剩余 $j$ 油的最小花费。然而这个题可以使用贪心，思想应该是基于：“每次只在最便宜的地方加油”，这样看来，DP 的状态是有浪费的，因为 DP 实际上决策了所有的决策，而很多点根本没有必要考虑加油。所以，什么时候用 DP，什么时候能贪心，是根据“决策冗余”来的。

代码

//  Created by Sengxian on 2016/11/02.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100 + 3;
double d[MAX_N], p[MAX_N], need[MAX_N];
double d1, c, d2, p0;
int n;

inline bool cmp(const int &i, const int &j) {
    return p[i] < p[j];
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    scanf("%lf%lf%lf%lf%d", &d1, &c, &d2, &p0, &n);
    d[n + 1] = d1, p[n + 1] = 1e60, p[0] = p0;

    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", d + i, p + i);
    for (int i = 0; i <= n + 1; ++i) d[i] /= d2;
    for (int i = 1; i <= n + 1; ++i)
        if (d[i] - d[i - 1] > c)
            return puts("-1"), 0;

    double oilLeft = 0;
    int i = 0, j = 0, mn;
    while (i <= n) {
        j = i + 2, mn = i + 1;
        while (j <= n + 1 && d[j] - d[i] <= c) mn = min(mn, j++, cmp);
        if (p[mn] < p[i]) { // 存在一个价钱比 i 小的加油站
            need[i] = d[mn] - d[i] - oilLeft, oilLeft = 0;
            i = mn;
        } else { // 否则一直开到最远的地方
            if (j == n + 2) need[i] = d[n + 1] - d[i] - oilLeft, oilLeft = 0;
            else need[i] = c - oilLeft, oilLeft = c - (d[j - 1] - d[i]);
            i = j - 1;
        }
    }
    double ans = 0;
    for (int i = 0; i <= n; ++i) ans += p[i] * need[i];
    printf("%.2lf\n", ans);
    return 0;
}

BZOJ 1999 - [Noip2007]Core树网的核 UVa 10271 - Chopsticks

Sengxian's Blog

「NOIP 1999」旅行家的预算

描述

分析

代码