1105. 汽车加油

单点时限: 2.0 sec

内存限制: 256 MB

一辆汽车加满油后可行驶 n 公里。旅途中有若干个加油站。设计一个有效算法,指出应

在哪些加油站停靠加油,使沿途加油次数最少。对于给定的 n(n <= 5000) 和 k(k <= 1024) 个加油站位置,编程计算最少加油次数。

输入格式

第一行有 2 个正整数 n 和 k,表示汽车加满油后可行驶 n 公里,且旅途中有 k 个加油站。接下来的 1 行中,有 k+1 个整数,依次表示第 i 个加油站与第 i-1 个加油站之间的距离。且第 1 整数表示第一个加油站与起点的距离,起点时汽车已加满油。第 k+1 个整数表示目的地与最后一个加油站的距离。

输出格式

输出编程计算出的最少加油次数。如果无法到达目的地,则输出 “No Solution!”.

样例

Input
7 7
1 2 3 4 5 1 6 6
Output
4

416 人解决,496 人已尝试。

537 份提交通过,共有 918 份提交。

1.3 EMB 奖励。

创建: 13 年,7 月前.

修改: 3 年,2 月前.

最后提交: 2 天,4 小时前.

来源: N/A

题目标签