题解 | #To Fill or Not to Fill#

贪心：目标是花费最少，就从“油价”开始“贪”。

将加油站按油价升序排列，依次遍历，

让油价低的加油站出发走尽可能多的路，即走Cmax*Davg，走过的路在路程数组上标记一下，

若从一个加油站出发到最大距离之间有部分已经被走过，则去掉，剩下这段路按该加油站油价收费。

最后若路程数组还有未标记的路段，即没走完，说明不可达。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int Cmax = 0, D = 0, Davg = 0, N = 0;
    double Pi = 0.00;
    int Di = 0;
    multimap<double, int> stations;//加油站：油价 距离
    double res = 0.00;
    while(cin >> Cmax >> D >> Davg >> N){
        stations.clear();
        for(int i = 0; i < N; i++){
            cin >> Pi >> Di;
            stations.emplace(Pi, Di);
        }
        bool* way = new bool[D];//路程数组
        for(int i = 0; i < D; i++)
            way[i] = false;
        /*
        贪心：目标是花费最少，就从“油价”开始“贪”。
        将加油站按油价升序排列，依次遍历，
        让油价低的加油站出发走尽可能多的路，即走Cmax*Davg，走过的路在路程数组上标记一下，
        若从一个加油站出发到最大距离之间有部分已经被走过，则去掉，剩下这段路按该加油站油价收费。
        最后若路程数组还有未标记的路段，即没走完，说明不可达。
        */
        res = 0.00;
        //map默认按油价排序
        for(auto iter = stations.begin(); iter != stations.end(); iter++){
            int dis = 0;//该油站的油所行路程
            for(int i = iter->second; i < iter->second+Cmax*Davg && i < D; i++){
                if(way[i] == false){//未被走过
                    dis++;
                    way[i] = true;
                }
            }
            res += dis * iter->first / Davg;
        }
        //检查路是否走完
        bool finish = true;
        for(int i = 0; i < D; i++)
            if(way[i] == false){//不可达
                cout << "The maximum travel distance = " << i << ".00" << endl;
                finish = false;
                break;
            }
        
//         if(finish)printf("%.2lf\n", res);
        cout.setf(ios::fixed);
        if(finish)cout << setprecision(2) << res << endl;
        
        delete[] way;
    }
    return 0;
}