Problem C: To Fill or Not to Fill
题目链接：http://codeup.hustoj.com/problem.php?cid=100000584&pid=2
题目大意：
首先，我们通过输入可以获得：油箱的最大容量（Cmax），目的地距离杭州的距离（D）,一单位的油可以行驶的距离（Davg）,加油站的个数（N）。以及每个加油站对应的油价和距离杭州的距离。
我们要做的就是判断该车能否到达目的地，要是可以到达目的地，就输出达到目的地所需要最少的油费，否则输出该车能行驶的最远距离。
思路
一、首先判断该车能否到达目的地，分别考虑两种情况：
（1）起点根本就没有加油站，汽车无法启动
（2）中途两个加油站之间的距离大于加满油后汽车能够行驶的最大距离。（这里应考虑到当最后一个加油站距离终点的距离大于汽车行驶的最大距离的情况）
二、如果上面的两种情况都没有发生，我们就需要计算该车行驶到终点需要花费的最少油费。这道题考的是贪心算法，即在每一次选着加油站的时候，都选着最优的情况。
（1）这道题非常巧妙的一个做法就是将终点也视为一个加油站（距离为D,油价为0）。这样子做，许多情况都不用单独考虑了,比如刚刚提到的最后一个加油站到终点的距离。
（2）然后，再将加油站类型的数组按照加油站距离杭州的距离，由小到大排序。这样就相当于将所有的加油站按序放在了一条的笔直的公路上，再来考虑问题就非常的直观。
（3）然后，我们从起点开始，每次去选着最优的加油站，需要考虑的情况如下：
- 我们每次考虑的加油站仅限于汽车加满油时，可行驶范围内的加油站。
- 情况一：从当前站往后遍历，如果有一加油站的油价低于当前站的油价，就直接前往。注意：只需要比当前加油站的油价低即可，不需要去找最低的。
- 情况二：如果在范围内，没有一家加油站的油价比当前油价低。则寻找范围内油价最低的，要是有多个油价最低的，则选择离当前站最近的站即可。
（4）（3）中已经实现每次寻找最优的加油站了。接下来我们计算油费。
- 要是下一个站的油价比当前的站低，我们先要考虑剩余的油能否到达下一个站，能到达则不加油，否则，我们需要加油，油量只需要满足刚好到达下一站即可。
- 要是下一个站的油价比当前的站高或者一样，我们则需要在当前站加满油，前往下一站即可。
C++代码实现（AC）
#include<cstdio>
#include<algorithm>
using namespace std;
struct Station{
double price;//油的单价
double distance;//距离杭州的距离
}station[510];
bool cmp(Station a, Station b){
return a.distance < b.distance;
}
int main(){
freopen("input.txt", "r", stdin);
double Cmax; //油箱的最大容量
double D; //两地之间的距离
double Davg; //单位油可行使的距离
int N; //加油站的个数
double X; //若终点不可达，行驶的最远距离
while(scanf("%lf%lf%lf%d", &Cmax, &D, &Davg, &N) != EOF){
double ans = 0;
for(int i = 0; i < N; i++){
scanf("%lf%lf", &station[i].price, &station[i].distance);
}
station[N].distance = D;
station[N].price = 0.00;
sort(station, station+N+1, cmp);//按照距离从小到大排序
double maxDistance = Cmax * Davg;//最大行驶距离
/**
* 判断汽车是否能够行驶到终点
*/
if(station[0].distance > 0){ /*起点根本就没有加油站*/
X = 0;
printf("The maximum travel distance = %.2f\n", X);
return 0;
}else{/*中途两个加油站之间的距离大于加满油后汽车能够行驶的最大距离*/
for(int i = 1; i <= N; i++){
if(station[i].distance - station[i-1].distance > maxDistance){
X = station[i-1].distance + maxDistance;
printf("The maximum travel distance = %.2f\n", X);
return 0;
}
}
}
/*能够行驶到终点的情况下计算最小花费*/
double curDistance = 0;//当前已经行驶的距离
double remainGas = 0.0;//剩余的汽油
int curStation = 0;//当前所在的站
int nextStation = 0;//计划去的下一站
while(curDistance < D){
/**
* 寻找下一站
*/
//寻找可达范围内最远的一个加油站，从而确定所需要考虑的加油站的范围，这里的nextStation并不是真正的下一站
//在之后的两个for循环中，会寻找真正的下一站，为nextStation重新赋值
for(int i = curStation+1; i <= N; i++){
if(station[i].distance <= curDistance + maxDistance){
nextStation = i;
}
}
/*如果能找到下一个加油站，价格比当前油价低，自接前往*/
for(int i = curStation+1; i <= nextStation; i++){
if(station[i].price < station[curStation].price){
nextStation = i;
break;
}
}
//如果范围内的加油站价格都大于等于当前站，就加满油去范围内价格最低的加油站
//注意：如果有多个价格最低的加油站，则去离当前站最近的站。
if(station[nextStation].price >= station[curStation].price){
//因为nextStation在下面的for循环中会变，所以用临死变量temp标记范围内最后一个加油站
int temp = nextStation;
double minPrice = station[curStation+1].price;
//将下一个加油站先定为当前站的下一站，
//这样可以确保当有多个加油站价格都为最低时，我们取得是离当前站最近的哪一个
nextStation = curStation + 1;
for(int i = curStation+2; i <= temp; i++){
if(station[i].price < minPrice){
minPrice = station[i].price;
nextStation = i;
}
}
}
/**
* 计算油费
*/
if(station[nextStation].price < station[curStation].price){//如果下一站的价格比当前站低
if (remainGas*Davg >= station[nextStation].distance - curDistance) {//如果油还够行驶到下一站，则不加油
remainGas = remainGas - (station[nextStation].distance - curDistance) / Davg;
}else {//否则，加油，足够行驶到下一站即可
ans = ans + ((station[nextStation].distance - curDistance) / Davg - remainGas) * station[curStation].price;
remainGas = 0;
}
}else{//如果下一站的价格大于等于当前站，将油加满，前往下一站
ans = ans + (Cmax - remainGas) * station[curStation].price;
remainGas = Cmax - (station[nextStation].distance - curDistance) / Davg;
}
//更新当前站为下一站
curDistance = station[nextStation].distance;
curStation = nextStation;
}
printf("%.2f\n", ans);
}
return 0;
}
