【贪心算法】To Fill or Not to Fill

网址牛客

输入

For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=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: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.

输出

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 = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

测试样例

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
50 1300 12 2
7.10 0
7.00 600

749.17
The maximum travel distance = 1200.00

C++

#include
#include
#include
#include
#include
using namespace std;
//贪心
struct station{
    double d;
    double money;
};
bool compare(station x,station y){
    return x.d<y.d;
}
int main(){
    double cmax,d,avg;
    int n;
    while(scanf("%lf%lf%lf%d",&cmax,&d,&avg,&n)!=EOF){
        station stat[n+5];
        for(int i=0;i<n;i++){
            scanf("%lf%lf",&stat[i].money,&stat[i].d);
        }
        sort(stat,stat+n,compare);
        stat[n].money=0;
		stat[n].d=d;
        if(stat[0].d>0){
            printf("The maximum travel distance = 0.00\n");
            continue;
        }
        //分三类
        int k=0,j,index;
        int ok=1;
        double curgas=0;
        double sum=0;
        double minPrice;

        while(k<n){
            if((stat[k+1].d-stat[k].d)>cmax*avg){
                printf("The maximum travel distance = %.2lf\n",stat[k].d+cmax*avg);
                ok=0;
                break;
            }else{
                index=k;
                minPrice=stat[k].money;
                //1.使用当前油量即可达到一个比当前站价格更低的站
                for(j=k+1;stat[j].d-stat[k].d<=curgas*avg&&j<=n;j++){
                    if(stat[j].money<minPrice){
                        minPrice=stat[j].money;
                        index=j;
                    }
                }
                if(index!=k){
                    curgas-=(stat[index].d-stat[k].d)/avg;
                    //cout<
                    k=index;
                    continue;
                }
                index=k;
                //2.在当前站加一些油可以到达比当前站价格低的站，找最近的
                for(j=k+1;stat[j].d-stat[k].d<=cmax*avg&&j<=n;j++){
                    if(stat[j].money<stat[k].money){
                        index=j;
                        break;
                    }
                }
                if(index!=k){
      
                    sum+=((stat[index].d-stat[k].d)/avg-curgas)*stat[k].money;
 
                    k=index;
                    curgas=0;
                    continue;
                }
                //3.在当前站加满油，找到后续站中价格较低的站
                index=k;
                minPrice=1e18;
                for(j=k+1;stat[j].d-stat[k].d<=cmax*avg&&j<=n;j++){
                    if(stat[j].money<minPrice){
                        minPrice=stat[j].money;
                        index=j;
                    }
                }
                sum+=(cmax-curgas)*stat[k].money;
                curgas=cmax-(stat[index].d-stat[k].d)/avg;
                k=index;
            }

        }
        if(ok){
                printf("%.2lf\n",sum);
        }
        }
        return 0;
}

对着抄还写了一下午，我真的累了
要注意index的变换，以及计算sum，curgas时用的是什么