九度教程第25题
C语言源码：[cpp]
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define maxsize 600
double lengthcmax,pricemin,falg;
double cmax,length,davg;
int n;
typedef struct station
{
double price;
double length;
}station;
station sta[maxsize];
int cmp(const void *a,const void *b)
{
station *aa=(station *)a;
station *bb=(station *)b;
return aa->length>bb->length?1:-1;
}
int find(int i)
{
int j,fprice=INT_MAX;
double price=INT_MAX;
for(j=i+1;j<n&&sta[i].length+lengthcmax>=sta[j].length;j++)
{
if(sta[j].price<price&&sta[j].price<sta[i].price)
{
price=sta[j].price;
fprice=j;
}
}
if(fprice<n&&sta[fprice].price<sta[i].price)
return fprice;
else
return -1;
}
int findmin(int i)
{
int j,fprice=INT_MAX;
double price=INT_MAX;
for(j=i+1;j<n&&sta[i].length+lengthcmax>=sta[j].length;j++)
{
if(sta[j].price<price)
{
price=sta[j].price;
fprice=j;
}
}
if(fprice<n)
return fprice;
else
return -1;
}
void pri(int i,double oil)
{//初始值0，0
int j,k;
j=find(i);//找离i站距离在一箱油之内的比i站油价低的站
if(j!=-1)
{//如果找到了
k=i+1;
while(k<=j)
if(sta[k].price<sta[i].price)
break;
else
k++;//找距离i最近的比i油价低的站，驶向k站，到k站邮箱清空
pricemin+=((sta[k].length-sta[i].length)/davg-oil)*sta[i].price;
pri(k,0);
}
else
{//未找到
if(sta[i].length+lengthcmax>=sta[n].length)//如果距离终点在一箱油距离之内，直接驶向终点
pricemin+=((sta[n].length-sta[i].length)/davg-oil)*sta[i].price;
else
{
j=findmin(i);//找离i站距离在一箱油之内油价最低的站，加满油，驶向j站
pricemin+=(cmax-oil)*sta[i].price;
pri(j,cmax-(sta[j].length-sta[i].length)/davg);
}
}
}
int main()
{
int i;
while(scanf("%lf %lf %lf %d",&cmax,&length,&davg,&n)!=EOF)
{
lengthcmax=cmax*davg;
for(i=0;i<n;i++)
scanf("%lf %lf",&sta[i].price,&sta[i].length);
qsort(sta,n,sizeof(sta[0]),cmp);
sta[n].length=length;
sta[n].price=INT_MAX;
for(i=0;i<n;i++)
if(sta[i].length+lengthcmax<sta[i+1].length)
break;
if(sta[0].length!=0)
printf("The maximum travel distance = 0.00\n");
else
if(i<n)
{
if(sta[0].length==0)
printf("The maximum travel distance = %.2lf\n",sta[i].length+lengthcmax);
else
printf("The maximum travel distance = 0.00\n");
}
else
{
pricemin=0;
pri(0,0);
printf("%.2lf\n",pricemin);
}
}
return 0;
}
补充：软件开发 , C语言 ,
