加油问题.cpp

来自「一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是空的）。给定两个城市之间的距」· C++ 代码 · 共 66 行

#include "iostream.h"
int mincost(int n,float p[],float d[],float dis,float cost,float d2,float c)
{
	int i;
	float *a=new float[n];
	float *s=new float[n];
	d[n+1]=dis;
	for(i=1;i<=n;i++)
	{
		if(i>1)
			s[i]=s[i-1]+a[i-1]-(d[i]-d[i-1])/d2;
		else if(i==1)
			s[i]=0;
		int k=1;
		if(s[i]<(d[i+1]-d[i])/d2 && p[i]>=p[i+1])//如果到此站未加油前剩余不够走且油价比下一站贵
			a[i]=(((d[i+1]-d[i])/d2-s[i])<(c-s[i])?((d[i+1]-d[i])/d2-s[i]):(c-s[i]));
		else if(s[i]>=(d[i+1]-d[i])/d2 && p[i]>=p[i+1])//如果到此站未加油前剩余够走且油价比下一站贵
			a[i]=0;
		else if(p[i]<p[i+1])//如果此站比下一站便宜
		{
			do
			{
				k++;
			}while(p[i]<p[i+k] && k<n-i+1);
			if((d[i+k]-d[i])/d2<=c)
				a[i]=(d[i+k]-d[i])/d2-s[i];
			else if((d[i+k]-d[i])/d2>c)
				a[i]=c-s[i];
		}
		if(a[i]+s[i]<((d[i+1]-d[i])/d2))
		{
			cout<<"No Solution"<<endl;
			return 0;
		}
		else
			cost=cost+a[i]*p[i];
	}
	cout<<"最小耗费为："<<cost<<endl;
	return 0;
}

void main()
{
	float dis,c,d2;
	float cost=0.0;
	int n;
	int i,j;
	cout<<"输入AB的距离dis：";
	cin>>dis;
	cout<<"输入油箱容量c：";
	cin>>c;
	cout<<"输入一升油能走的距离d2：";
	cin>>d2;
	cout<<"输入油站总数n：";
	cin>>n;
	float *d=new float[n+1];
	cout<<"输入每个站到出发点的距离d[i]："<<endl;
	for(i=1;i<=n;i++)
		cin>>d[i];
	float *p=new float[n+1];
	cout<<"输入每个站的汽油单价p[j]："<<endl;
	for(j=1;j<=n;j++)
		cin>>p[j];
	mincost(n,p,d,dis,cost,d2,c);
}