题目给出的测试样例
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
分析
| 编号 | 距离 | 价格 | 剩余油量可行驶距离 | 可到达范围内最便宜站nxt | 加油量 | 花费价格 |
|---|---|---|---|---|---|---|
| 0 | 0 | 7.1 | 0 | 1 | 加到1，即150km量 | 88.75 |
| 1 | 150 | 7.0 | 0 | 3 | 加到3量，即150km量 | + 87.5=176.25 |
| 2 | 200 | 7.2 | 50 | 3 | pass | pass |
| 3 | 300 | 6.85 | 0 | 没有更廉价且到不了终点 | 加满，即600km量 | + 342.5 = 518.75 |
| 4 | 400 | 7.5 | 500 | 5 | 可以到5不加 | pass |
| 5 | 600 | 7.0 | 300 | 没有更廉价且到不了终点 | 加满，即300km量 | +175=693.75 |
| 6 | 1000 | 7.3 | 200 | 7 | 加到7量，即50km的量 | +30.14=724.17 |
| 7 | 1250 | 6.0 | 0 | 没有更廉价且能到终点 | 加到终点，即50km量 | +25=749.17 |
*价格有舍入
AC代码
#include<bits/stdc++.h>
using namespace std;
struct gas{
double pos, price;
bool operator < (const gas x) const{
return pos < x.pos;
}
};
int main(){
int n;
double target, davg, cmax;
scanf("%lf %lf %lf %d", &cmax, &target, &davg, &n);
vector<gas> data(n);
for(int i=0; i<n; i++) scanf("%lf %lf", &data[i].price, &data[i].pos);
sort(data.begin(), data.end()); //按路程远近排序
double posnow=0, cnow=0, cost=0;
for(int i=0; i<n; i++){
if(posnow+cnow*davg<data[i].pos){ //现在的油无法到达下一个加油站，旅途结束
printf("The maximum travel distance = %.2lf\n", posnow+cnow*davg);
return 0;
}
cnow -= (data[i].pos - posnow)/davg; //开到下一个加油站
posnow = data[i].pos;
int nxt=i;
for(int j=i; j<n&&data[j].pos<cmax*davg+posnow&&data[j].pos<target; j++){ //在能到达的最大的范围内，搜索有没有比当前加油站更便宜的站
if(data[nxt].price>data[j].price){ nxt = j;break;} //要找第一个更便宜的站，不然会贵一点，给出的测试用例会花费750多
}
if(nxt==i){ //如果没有更便宜的加油站
if(cmax*davg+posnow < target){ //如果还没到终点就加满
cost += data[i].price*(cmax-cnow);
cnow = cmax;
}
else{ //如果可以到终点就加到终点的油
cost += data[i].price*(target-posnow-cnow*davg)/davg;
printf("%.2lf\n", cost);
return 0;
}
}
else{ //如果找到更便宜的加油站
if(data[nxt].pos>posnow+cnow*davg){ //这个加油站目前的油开不到，加需要开到这个加油站的油
cost += data[i].price*(data[nxt].pos-posnow-cnow*davg)/davg;
cnow += (data[nxt].pos-posnow-cnow*davg)/davg;
}
i = nxt-1; //直接跳到下一个最廉价加油站，中间的加油站不考虑
}
}
printf("The maximum travel distance = %.2lf\n", posnow+cnow*davg);
return 0;
}
