贪心算法作业之汽车加油问题

啰嗦几句

好不容易写到最后一个作业，感觉好没意思，都是直接写代码，这个关于贪心算法，实在写不下去了。但是，不知道写什么东西，凑个数。

问题描述

一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。

代码如下

#include<iostream>
#include <vector>
using namespace std;
using std::vector;
double greedy(vector<int>x,int n)
{
int sum=0,k=x.size();
    for(int j=0;j<k;j++)
        if(x[j]>n)
    {
        cout<<"No solution!"<<endl;
        return -1;
    }
    int s=0;
    for (int i=0;i<k;i++)
    {
        s+=x[i];
        if(s>n)
        {
            sum++;
            s=x[i];
        }
    }
     return sum;
}
int main()
{
    int i,k,n;
    int a;
    int t;
    vector<int>x;
    cout<<"请输入加油站数目:"<<endl;
    cin>>k;
    cout<<"请输入汽车加满油可行驶最远距离:"<<endl;
    cin>>n;
    cout<<"请输入加油站之间的距离:"<<endl;
    for(i=1;i<=k+1;i++)
    {
        cin>>a;
        x.push_back(a);
   }
   t=greedy(x,n);
   cout<<"最少加油次数是:"<<t<<endl;
   return 0;
}