汽車加油問題（貪心算法）

1.問題描述：一輛汽車加滿油後可行駛nkm。旅途中有若幹加油站。設計一個有效算法，指出應在哪些加油站停靠加油，使沿途加油次數最少。

算法設計：對于給定的n和k個加油站位置，計算最少加油次數。

資料輸入：n：表示汽車加滿油後可行駛nkm

          k：旅途中有k個加油站

         k+1個整數：表示第k個加油站與第k-1個加油站之間的距離。第0個加油站表示出發地，汽車已加滿油。第k+1個加油站表示目的地。

資料輸出：最少加油次數和具體在哪幾個加油站加油。

例如： n=7  k=7

  K+1個整數：1 2 3 4 5 1 6 6

最優值：4

2.相關代碼：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n, k;
	while (cin >> n >> k)
	{
		vector<int>v;
		v.push_back(0);
		for (int i = 1; i <= k+1; i++)
		{
			int dist;
			cin >> dist;
			v.push_back(dist);
		}
		int sum = n;
		int  cnt = 0;
		cout << endl;
		for (int i = 0; i <= k; i++)
		{
			int j = i + 1;
			if (sum < v[j])
			{
				sum = n;
				if(sum<v[j])
					cout << "no solution" << endl;
				else
				{
					cnt++;
					sum -= v[j];
					cout  << "第" << i << "次" << endl;
				}
			}
			else
				sum -= v[j];
		}
		cout << cnt << endl;
	}
	return 0;
}
/*
7 7
1 2 3 4 5 1 6 6
*/