A 1033 To Fill or Not to Fill（官网+牛客全AC）

题目链接

Problem Description

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input

Each input file contains one test case. For each case, the first line contains 4 positive numbers: C​_max​​ (≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; D​_avg​​ (≤20), the average distance per unit gas that the car can run; and N (≤ 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: P​_i​​ , the unit gas price, and D​_i​​ (≤D), the distance between this station and Hangzhou, for i=1,⋯,N. All the numbers in a line are separated by a space.

Output

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print The maximum travel distance = Xwhere Xis the maximum possible distance the car can run, accurate up to 2 decimal places.

Sample Input 1:

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

Sample Output 1:

749.17

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

The maximum travel distance = 1200.00

题目大意：

初始车辆没有油，给出油箱容量、终点距离（起点、终点、加油站在一条直线上）、每单位油能行驶的距离、加油站数量N。然后输入N个加油站的油价和距离。如果能到达终点，输出花费最少的加油费；否则输出能到达的最远距离。

解题思路：

将终点当成一个距离为D、油价为0的加油站，对所有加油站按距离从小到大排序，然后按以下条件查找下一个到达的加油站，代码中的i表示当前加油站的下一个加油站：

1. 判断距离最近的那个加油站是否可达，如果不可达，输出当前加油站距离+满油状态最大行驶距离
2. 找到第一个可达且油价比当前油价小的加油站ind，做标记，在当前加油站加够从当前距离行驶到ind加油站的油量，当前距离更改为ind加油站的距离，当前加油站更改为ind
3. 如果2没找到，则遍历所有可达的加油站，找到价格最小的加油站minn，把油箱加满，当前距离更改为当前加油站满油状态可达的最远距离，当前加油站更改为minn

AC代码

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

struct node{
    double price;
    int dis;
};

bool cmp(const node &a,const node &b){
    return a.dis!=b.dis ? a.dis<b.dis : a.price<b.price;
}

int main(){
    int Cmax,D,Davg,N,Di,nowdis,maxgo;
    double nowprice,ans=0;
    scanf("%d%d%d%d",&Cmax,&D,&Davg,&N);
    maxgo=Cmax*Davg;
    vector<node> gas(N+1);
    gas[0].dis=D;
    gas[0].price=0.0;
    for(int i=1;i<=N;i++){
        scanf("%lf%d",&gas[i].price,&gas[i].dis);
    }
    sort(gas.begin(),gas.end(),cmp);
    if(gas[0].dis!=0){
        printf("The maximum travel distance = 0.00");
        return 0;
    }else{
        nowdis=0;
        nowprice=gas[0].price;
    }
    int i=1;
    while(nowdis<D){ //判断最近一个是否可达, 找出可达且油价比现在小的第一个站, 如果没找到就加满然后去可达的油价最小的站
        if(gas[i-1].dis+maxgo<gas[i].dis){
            printf("The maximum travel distance = %.2f",(double)(nowdis+maxgo));
            return 0;
        }
        int ind=-1,st=i;
        for(;i<=N;i++){
            if(gas[st-1].dis+maxgo>=gas[i].dis && gas[i].price<nowprice){
                ind=i++;
                break;
            }
        }
        if(ind==-1){
            i=st;
            double minp=INF;
            int minn;
            while(i<=N && gas[st-1].dis+maxgo>=gas[i].dis){
                if(gas[i].price<minp){
                    minp=gas[i].price;
                    minn=i;
                }
                i++;
            }
            ans+=(double)(gas[st-1].dis+maxgo-nowdis)*nowprice;
            nowdis=gas[st-1].dis+maxgo;
            nowprice=gas[minn].price;
            i=minn+1;
        }else{
            ans+=(double)(gas[ind].dis-nowdis)*nowprice;
            nowdis=gas[ind].dis;
            nowprice=gas[ind].price;
        }
    }
    printf("%.2f",ans/Davg);
    return 0;
}