ACWing3659:燃油补给问题

https://www.acwing.com/problem/content/3662/

一辆汽车加满油后可行驶n公里。该车从起点S出发，目标是到达终点E。在这条路线中，分布着k个加油站。已知从起点到第一个加油站的距离为l1公里，第一个加油站到第二个加油站的距离为l2公里，依此类推，最后一个加油站到终点E的距离为lk+1公里。为了保证汽车能够顺利到达终点，请计算汽车至少需要在多少个加油站加油？假设汽车在出发时油箱是满的。

输入格式：
输入包括多组测试数据。每组数据的第一行包含两个整数n和k，分别表示汽车加满油后的最大行驶距离和加油站的数量。第二行包含k+1个整数l1, l2, ..., lk+1，分别表示从起点到第一个加油站、各加油站之间的距离以及最后一个加油站到终点的距离。

输出格式：
对于每组数据，如果汽车可以到达终点，则输出一个整数表示最少需要加油的次数；如果无法到达终点，则输出“No Solution”。

数据范围：
1 ≤ n, k ≤ 5000
1 ≤ li ≤ 10000

解决思路：
我们可以将n视为汽车的最大油量，li视为每段路程的耗油量。如果某段路程的耗油量超过了汽车的最大油量n，那么汽车就无法完成这段行程。反之，我们只需要在油量不足以支持下一段路程时进行加油，并记录加油次数。这种方法基于贪心算法，即每次在必要时加油，以确保总是在最合适的时机进行加油，从而达到最少加油次数的目标。

#include 
using namespace std;
const int N = 5010;
int a[N];
int n, k;
int main() {
    while (scanf("%d%d", &n, &k) != EOF) {
        for (int i = 1; i <= k + 1; i++) scanf("%d", &a[i]);
        int res = 0, oil = n;
        bool canReach = true;
        for (int i = 1; i <= k + 1; i++) {
            if (a[i] > n) {
                canReach = false;
                break;
            }
            if (oil                 res++;
                oil = n;
            }
            oil -= a[i];
        }
        if (canReach) printf("%d\n", res);
        else puts("No Solution");
    }
    return 0;
}

该算法的时间复杂度为O(k)，其中k为加油站的数量，适用于题目给定的数据规模。