Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
汽车加油问题
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 65, Accepted users: 63
Problem 10305 : No special judgement
Problem description
  一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应 在哪些加油站停靠加油,使沿途加油次数最少。并证明算法能产生一个最优解。 对于给定的n和k个加油站位置,编程计算最少加油次数。

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

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

Sample Input
7 7
1 2 3 4 5 1 6 6
Sample Output
4
Submit   Clarifications   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:18310 today,16241301 total, since 2010-05-07