【问题描述】

一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。并证明你的算法能产生一个最优解。

【输入形式】

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

【输出形式】

第一行输出编程计算出的最少加油次数，第二行输出汽车会在哪几个加油站加油，如果无法到达目的地，则输出”NoSolution”

【样例输入】

4 5
2 3 1 2 2 3

【样例输出】

3
1 3 5

c++代码

#include<iostream>
using namespace std;
int main()
{
    int n,k;
    int a[100];
    int b[100];
    cin>>n>>k;
    int num=0,s=n;
    for(int i=0;i<=k;i++)
    {
         cin>>a[i];
    }
    for(int i=0;i<=k;i++)
    {
        if(a[i]>n)
         {
             cout<<"No Solution";
             return 0;
         }
         if(s-a[i]>=0)
         {
             s-=a[i];
         }
         else
         {
             num++;
             s=n-a[i];
             b[num]=i;
         }
    }
    cout<<num<<endl;
    for(int i=1;i<=num;i++)
    {
    	cout<<b[i]<<" ";
	}
    return 0;
}