汽车加油问题
一、问题描述
一辆汽车加满油后可行驶。路途中有个加油站。设计一个有效算法，指出应在那些加油站停靠加油，使得沿途加油次数最少。
二、简要分析
启程前汽车已经加满油。对于给定，设加油站与加油站的间距表示为(加油站表示起点，加油站表示终点)
1.若始发点与终点的间距，则汽车途中不必加油，加油次数。
2.若始发点与终点的间距，且加油站等间距时，则有：
a.若，则最少加油次数为，即每个加油站都要停靠加油；
b.若，则汽车不能到达终点，因汽车到达不了下一个加油站加油；
3.始发点与终点间距,且加油站间不全等距的情况是我们要解决的。
三、解决策略
汽车是由起点向终点行驶，现在面对的问题是应该在那个加油站加油，可使旅途过程中加油次数最少。为了解决该问题，我们可以规定在油箱中的油不足以使汽车行驶到下一个加油站的前提下，才加一次加油，如此进行方可使汽车加油次数达到最小，即贪心策略。
贪心策略的基本思想：汽车途中加油次数最少，即是求解最优解问题；贪心策略每一步都是建立在局部最优的基础上，每一步选择都是对当前解的一个扩展，直到获得问题的完整解，即使此法不一定能得到整体最优，却可以用来近似最优解。贪心法具有最优子结构性质和贪心选择性质。
四、代码实现（C#）
namespace ConsoleApplication1
{启程汽车
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("请输入汽车加满油后可行驶路程： ");
            int n = Convert.ToInt32(Console.ReadLine());
            Console.Write("请输入途经加油站总数： ");
            int k = Convert.ToInt32(Console.ReadLine());
            int[] distance = new int[k + 1];//加油站间距
            int[] note = new int[k];//记录加油站点
            Console.WriteLine("请输入加油站间距！");
            for (int i = 0; i <= k; i++)
            {//从始点起，加油站间距
                Console.Write("站点间距{0}:  ", i + 1);
                distance[i] = Convert.ToInt32(Console.ReadLine());
            }
            int count;//记录加油次数
            Problem p = new Problem();
            count = p.Greedy(distance, note, n);
            if (count >= 0)
            {
                if (count == 0)
                    Console.WriteLine("汽车不用加油就可到达终点！");
                else
                {
                    Console.WriteLine("汽车在旅途中需加{0}次油！", count);
                    Console.WriteLine("分别在以下加油站加了油：");
                    for (int i = 0; i < note.Length; i++)
                    {
                        if (note[i] != 0)
                        {//输出需加油站点
                            Console.WriteLine("第" + note[i] + "个加油站！");
                        }
                    }
                }
            }
            else
                Console.WriteLine("汽车无法到达终点！");
            Console.ReadKey();
        }
    }
    class Problem
    {
        public int Greedy(int[] d, int[] note, int n)
        {
            int i, j, s, add = 0, p = 0, k = d.Length;
            for (i = 0; i < k; i++)
            {
                if (d[i] > n)
                {//不能到达目的地
                    return -1;
                }
            }
            for (j = 0, s = 0; j < k; j++)
            {
                s += d[j];
                if (s > n)
                {//需要加油
                    add++;
                    note[p++] = j;
                    s = d[j];
                }
            }
            return add;
        }
    }
}
五、实例
汽车加满油后可行驶，途中加油站个数，加油站及间距如下所示：
代码运行实现结果：
六、时间复杂度分析
因为需要知道汽车要在那个加油站加油，所以需要遍历所有加油站，即时间复杂度为。