汽车加油

题目描述

汽车从 A 到 B，沿途有 $n$ 个加油站；满箱油可跑 $m$ 公里，出发满箱、每次加油都加满。多组数据读到文件尾：每组第一行 $n, m$ ，第二行 $n+1$ 个实数 $d_1,\dots,d_{n+1}$ ， $d_i$ 为站 $i-1$ 到站 $i$ 的距离（ $0$ 号站为 A、 $n+1$ 号站为 B）；输出最少加油次数与加油总量。样例输入 5 15 与 5 7 5 2 6 4，输出 2 25。

思路

从满箱出发逐段消耗：油够就开下一段；不够走下一段时在当前站补满（补入量 $= m -$ 当前油量），次数加一。出发那箱不计入答案；数据中存在超过 $m$ 的段，按此规则递推，油量允许为负。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 15:41
# update_at: 2026-10-02 15:41

import sys


def num(token: bytes) -> int | float:
    """题面写"实数"，整数 token 原样返回，带小数点的才转 float。"""
    return float(token) if b"." in token else int(token)


def fmt(value: int | float) -> str:
    """整值去掉 .0，与样例的整数输出保持一致。"""
    return str(int(value)) if float(value).is_integer() else str(value)


def min_refuel(segs: list[int | float], capacity: int | float) -> tuple[int, int | float]:
    """贪心扫每段路：油不够走下一段时，在当前站加满；返回加油次数与加油总量。

    只在"被迫"时加油，且一加就加满、加在最后到达的站上——这既不增加次数
    （更晚加油不会让后面更早缺油），也给出每次能走的最长距离，故次数最少。
    """
    tank = capacity   # 出发时油箱满，这一箱不计入加油量
    cnt = 0
    total = 0
    for d in segs:
        if tank >= d:
            tank -= d
        else:
            total += capacity - tank  # 把剩下的油补满：加了多少 = 缺了多少
            tank = capacity - d       # 加满后立刻开过这一段（单段超续航时可为负，与题解口径一致）
            cnt += 1
    return cnt, total


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    out: list[str] = []
    while True:
        try:
            n = int(next(tokens))          # 加油站个数
            capacity = num(next(tokens))   # 满箱可跑公里数 = 油箱容量（1 升 1 公里）
        except StopIteration:
            break                          # 多组数据读到文件尾
        segs = [num(next(tokens)) for _ in range(n + 1)]  # n+1 段路的距离
        cnt, total = min_refuel(segs, capacity)
        out.append(f"{cnt} {fmt(total)}")
    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:30
 * update_at: 2026-10-06 16:30
 */
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

ll n;                 // 加油站个数，路线共 n+1 段
double capacity;      // 满箱油能跑的公里数 = 油箱容量（1 升跑 1 公里）
double d[MAXN];       // d[i] 为第 i-1 站到第 i 站的距离，i = 1..n+1

// 输出一个数值：整值去掉小数点，非整值原样输出（与样例的整数格式一致）
void print_value(double v) {
    double rounded = floor(v + 0.5);
    if (fabs(v - rounded) < 1e-9) {
        printf("%.0f", rounded);
    } else {
        printf("%g", v);
    }
}

int main() {
    while (scanf("%lld", &n) == 1) {
        scanf("%lf", &capacity);
        for (ll i = 1; i <= n + 1; i++) {
            scanf("%lf", &d[i]);
        }

        // 贪心扫每段路：油够就开，不够就在当前站补满（补入量 = 满箱 - 当前油量）
        double tank = capacity;   // 出发时满箱，这一箱不计入次数与总量
        ll cnt = 0;               // 加油次数
        double total = 0;         // 加油总量
        for (ll i = 1; i <= n + 1; i++) {
            if (tank >= d[i]) {
                tank -= d[i];
            } else {
                total += capacity - tank;  // 补满：加了多少 = 缺了多少
                tank = capacity - d[i];    // 加满后立刻开过这一段
                cnt++;
            }
        }

        printf("%lld ", cnt);
        print_value(total);
        printf("\n");
    }
    return 0;
}

目录

题目描述

思路

参考代码