level 1
#include <stdio.h>
#include <string.h>
typedef struct{
float price;
float Dis;
}Dot;
void Sort_MergeRec(Dot* array,int num,Dot* temparray){
if (num!=1){
int i=0,j=0,k=0,l=num/2,r=num-num/2;
Sort_MergeRec(array,l,temparray);
Sort_MergeRec((array+num/2),r,(temparray+num/2));
do{
*(temparray+(i++))=((array+j)->Dis)<(array+l+k)->Dis?*(array+(j++)):*(array+l+(k++));
} while(j<l&&k<r);
if(j==l) memcpy(temparray+l+k,array+l+k,sizeof(Dot)*(r-k));
else memcpy(temparray+j+r,array+j,sizeof(Dot)*(l-j));
memcpy(array,temparray,num*sizeof(Dot));
}
}
void Sort_Merge(Dot* array,int num){
Dot TempArray[num];
Sort_MergeRec(array,num,TempArray);
}
int main(void){
Dot dot[8];
int NumDot,i;
float CapFuel,ConsumePerKm,kmperL,DistanceTotal,SumBudget=0,Endurance;
//printf("DistanceTotal CapFuel ConsumePerKm StatPrice NumDot\n");
scanf("%f %f %f %f %d",&DistanceTotal,&CapFuel,&kmperL,&dot[0].price,&NumDot);
ConsumePerKm=1/kmperL;
dot[0].Dis=0.0;//起始点
dot[(NumDot)+1].price=-1.0;//终点加油最便宜,在终点的油量为0
dot[(NumDot)+1].Dis=DistanceTotal;//终点
Endurance=CapFuel/ConsumePerKm;
//printf("Endurance=%f\n",Endurance);
for(i=0;i<NumDot;i++){
//printf("第%d点距离 单价 \n",i+1);
scanf("%f %f",&dot[i+1].Dis,&dot[i+1].price);
}
//按距离为点排序
if(NumDot) Sort_Merge(dot,NumDot+1);
//
float EndurRem=0;
for(i=0;i<NumDot+1;i++){//计算每个点要加多少里程燃油
float CheapPrice = dot[i].price,gap=0.0;
if(i) EndurRem-=dot[i].Dis-dot[i-1].Dis;
if(Endurance<dot[i+1].Dis-dot[i].Dis){
//printf("到不了一点 Inreachable!\n");//到不了一点
printf("No Solution\n");//到不了一点
break;
}
int j;
for( j=i+1;j<NumDot+2;j++){
if(dot[j].Dis<dot[i].Dis+Endurance){
if(dot[j].price<CheapPrice) {//如果有比当前便宜的最近站点
gap=dot[j].Dis-dot[i].Dis-EndurRem;//确定在那个站点加油
if(gap<0) {
gap=0;//没有比之前加油站点便宜
break;
}
//printf("在%d点加%fkm的油到%d点花费%f\n",i,gap,j,gap*ConsumePerKm*dot[i].price);
EndurRem+=gap;
SumBudget+=gap*ConsumePerKm*dot[i].price;//在此站点加能到达哪个站点的油
break;
}
}
else {//没找到,加满油
//printf("在%d点加满油\n",i);
SumBudget+=(Endurance-EndurRem)*ConsumePerKm*dot[i].price;
EndurRem=Endurance;
break;
}
}
}
if(i==NumDot+1) printf("%.2f\n",SumBudget);
return 1;
}
2025年02月19日 05点02分
