main.cpp

用C语言实现的算法题中的加油问题。 用贪心算法实现的。

#include "stdio.h"
#define MAXSIZE 1000

int main()
{
	int search(double dis[],double price[],double content,double distance2,int n);
	int k=1,l;//数据组数
	int i;//i用来循环
	double distance1,content,distance2;//A到B的距离，油箱容量，每升油能走的距离
	int n;//沿途油站数
	double dis[MAXSIZE+1]={0};//用来存放各站点到起点的距离
	double price[MAXSIZE+1]={0};
	scanf("%d",&l);
	while(k<=l)
	{
		scanf("%lf%lf%lf%d",&distance1,&content,&distance2,&n);
		for(i=1;i<=n;i++)
			scanf("%lf",&dis[i]);
		dis[i]=distance1;
		for(i=1;i<=n;i++)
			scanf("%lf",&price[i]);
		price[i]=0;
		search(dis,price,content,distance2,n);
		k++;
	}
	return 1;
}


int search(double dis[],double price[],double content,double distance2,int n) 
{
	int i,j=0;//用与循环
	double total=0.0;//总共的油价
	double temp;//存放邮箱里的剩余油量
	temp=0.0;
	for (i=1;i<=n;i++)
	{
		j=i+1;
		temp=temp-(dis[i]-dis[i-1])/distance2;
		if(distance2*content<dis[i+1]-dis[i])
		{
			printf("No Solution\n");
			return 0;
		}
		while((price[i]<price[j])&&(j<=n+1))
			j++;
		if(dis[j]-dis[i]<=content*distance2)
		{
			if(temp*distance2>=dis[j]-dis[i])
			{
//				temp=temp-(dis[i]-dis[i-1])/distance2;
				total=total;
			}
			else
			{
				total=total+((dis[j]-dis[i])/distance2-temp)*price[i];
				temp=(dis[j]-dis[i])/distance2;
			}
		}
		if(dis[j]-dis[i]>content*distance2)
		{
			total=total+content*price[i];
			temp=content;
		}
	}
	printf("%.1lf\n",total);
	return 1;
}