题目分析
Input:
第一行:Cmax D Davg N
接下来的N行:Pi Di
Output:(accurate up to 2 decimal place)
Case1:minimum price
Case2:The maximum travel distance = xxx
贪心策略
- 在distance=0的地方必须有加油站
- 在distance=D的地方(终点),油箱里油的剩余量必须为0
- 假设某一站为A,则如果在A加满油,能行驶的最远距离为maxDis=Cmax*Davg
- 使用leftGas变量来记录剩余油量
- 在A.distance~A.distance+maxDis之间寻找第一个比A便宜的站,如果找到,记为B,则在A加刚好行驶至B的油量
- 若没有符合情况1的站,但是有终点,则在A加刚好可以行驶至终点的油量
- 若没有符合情况1和情况2的站,则找一个站C,C.price在相应范围内最小,在A加满油,行驶至C
- 不是情况1、2、3的任何一种情况,则行驶的最大距离为A.distance+maxDis
C++源码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 99999
typedef struct Station
{
double price;
double distance;
}Station;
// the pointer tempA can point to a value of any type but the value must be a constant
int cmp(const void* tempA,const void* tempB)
{
Station *a = (Station*)tempA;
Station *b = (Station*)tempB;
return a->distance - b->distance;
}
int main()
{
int N;
double Cmax, D, Davg;
cin>>Cmax>>D>>Davg>>N;
Station *stations = new Station[N+1];
for(int i = 0; i < N; i++)
{
cin>>stations[i].price>>stations[i].distance;
}
stations[N].price = INF;
stations[N].distance = D;
qsort(stations, N+1, sizeof(Station), cmp);
// if there is no station at the beginning
if(stations[0].distance != 0)
{
cout<<"The maximum travel distance = 0.00"<<endl;
return 0;
}
double maxDis = Cmax * Davg;
double minPrice = 0;
double leftGas = 0;
// station index indicates where the car is now, the initial value is 0
int index = 0;
while(index != N)
{
int intermedia = -1;
int caseFlag = 0;
int boundFlag = -1;
for(int i = 0; i <= N; i++)
{
if(stations[index].distance <= stations[i].distance && stations[i].distance <= stations[index].distance + maxDis)
{
boundFlag = i;
if(stations[i].price < stations[index].price)
{
if(intermedia == -1)
{
intermedia = i;
caseFlag = 1;
}
}
}
}
if(caseFlag == 1)
{
minPrice = minPrice + stations[index].price * (((stations[intermedia].distance - stations[index].distance) / Davg) - leftGas);
leftGas = 0;
index = intermedia;
}
else if(caseFlag != 1 && stations[index].distance <= D && D <= stations[index].distance + maxDis)
{
caseFlag = 2;
minPrice = minPrice + stations[index].price * ((D - stations[index].distance) / Davg - leftGas);
printf("%.2lf\n", minPrice);
leftGas = 0;
index = N;
return 0;
}
else if(caseFlag != 1 && caseFlag != 2)
{
if(boundFlag == index)
{
// caseFlag = 4;
printf("The maximum travel distance = %.2lf\n", stations[index].distance + maxDis);
return 0;
}
else
{
caseFlag = 3;
double tempMinPrice = stations[index+1].price;
for(int i = index + 1; i <= boundFlag; i++)
{
if(stations[i].price <= tempMinPrice)
{
tempMinPrice = stations[i].price;
intermedia = i;
}
}
minPrice = minPrice + stations[index].price * (Cmax - leftGas);
leftGas = Cmax - (stations[intermedia].distance - stations[index].distance) / Davg;
index = intermedia;
}
}
}
}
网友评论