4.16.cpp

数据结构中的贪心算法

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
	int n,k;//加油后可行驶的里程,加油站的个数
	int i,sum;
	int m=0;  //记录加油的次数
    
	cout<< "请输入汽车加满油后行驶的最大公里数n:";
    cin>>n;
    cout<< "请输入加油站个数k:";
    cin>>k;
	
	cout<<"请输入各加油站之间间隔公里数：";


	int *a=new int[k+1];
	for(i=0;i<=k;i++)
	{
		cin>>a[i];
	 
	}


  
	sum=0;
	
	for(i=0;i<=k;i++)
	{
		if(a[i]>n){cout<<"No Solution!\n";break;}
		else{
			sum+=a[i];
		    if(sum<=n)continue;
			else {
							
				sum=a[i];
				m++;         //记录加油的次数
		
			}
		}
	}
    
	cout<<"我们得到的最少加油次数："<<m<<endl;
	system("pause");
	delete[]a;
    return 0;
   
}