【贪心】九度OJ 1437：To fill or not to fill

一、题目内容

题目描述：

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.

输入：

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

二、代码及注释

#include<stdio.h> #include<algorithm> using namespace std; /** 1.先对station的end赋值，超过ddis的赋值为ddis 2.按dis排序 3.定义剩余，总价 4.如果第一个加油站不在0，则到不了 5.下一个最近的加油站在最远距离以外，到不了 6.最后一个加油站的最远距离到不了终点 7.下一个加油站刚好是当前的最远距离 8.在该站的最远距离中，有比当前更便宜的，只加油刚好到那一站 9.没有比当前更便宜的,并且当前站点可以到终点，就一路开到底 10.没有比当前更便宜的，下一站就选不包括本站在内最便宜的,当前加满油箱 11.记得更新ability剩余量 **/ struct Station{ float price; float dis; float end; bool operator < (const Station & A) const{ return dis< A.dis; } }buf[502]; int main(){ int n; float cmax,ddis,davg; while(scanf("%f %f %f %d",&cmax,&ddis,&davg,&n)!=EOF){ for(int i=0;i<n;i++){ scanf("%f %f",&buf[i].price,&buf[i].dis); //如果这个加油站的最远距离超出终点 if(buf[i].dis+cmax*davg>=ddis){ buf[i].end=ddis; }else{ buf[i].end=buf[i].dis+cmax*davg; } } sort(buf,buf+n); float ability=0;//到下一站时候的剩余 float totalprice=0;//总价 //如果第一个加油站不在起点，到不了 if(buf[0].dis>0){ printf("The maximum travel distance = 0.00\n"); continue; } for(int i=0;i<n;){ int j=i+1; //下一个最近的加油站在最远距离以外，到不了 if(buf[j].dis>buf[i].end){ // printf("buf[j].dis=%d buf[i].end=%d\n",buf[j].dis,buf[i].end); printf("The maximum travel distance = %.2f\n",buf[i].end); break; } //最后一个加油站的最远距离到不了终点 if(i==n-1&&ddis>buf[i].end){ printf("The maximum travel distance = %.2f\n",buf[i].end); break; } //下一个加油站刚好是当前的最远距离 if(buf[j].dis==buf[i].end){ totalprice+=(cmax*davg-ability)/davg*buf[i].price; ability=0; i=j; continue; } int flag=0;//标志是否在当前最远距离内有更便宜的加油站 //有比当前更便宜的，只加油刚好到那一站 if(i<n-1){ while(j<=n-1&&buf[j].dis<=buf[i].end){ if(buf[j].price<=buf[i].price){ flag=1; totalprice+=(buf[j].dis-buf[i].dis-ability)/davg*buf[i].price; i=j; ability=0; break; } j++; } } int k=i+1; float min=buf[k].price; //寻找第二小价格，初始化为下一站的价格 int mink=k; //第二小价格的车站下标 if(flag==0){ //没有比当前更便宜的,并且当前站点可以到终点，就一路开到底，这一点别忘了！！ if(buf[i].end==ddis){ totalprice+=(ddis-ability-buf[i].dis)/davg*buf[i].price; printf("%.2f\n",totalprice); break; } //没有比当前更便宜的，下一站就选不包括本站在内最便宜的,当前加满油箱 for(;k<j;k++){//这里是<j if(buf[k].price<min){ min=buf[k].price; mink=k; } } totalprice+=(cmax*davg-ability)/davg*buf[i].price; //下边这两个语句注意先后顺序！！！ ability=buf[i].end-buf[mink].dis; i=mink; } } } }