题目:http://pat.zju.edu.cn/contests/pat-a-practise/1033
题解:
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<algorithm> using namespace std; #define INF 0x6fffffff struct point { double price; double distance; } node[505]; bool cmp(const struct point &a,const struct point &b) { return a.distance<b.distance; } int main() { double cmax,davg,d,nowCapacity,minPrice,summ; int n,idx; double len;//满邮箱最长行驶距离 bool flag; scanf("%lf%lf%lf%d",&cmax,&d,&davg,&n); len=cmax*davg; for(int i=0; i<n; ++i) scanf("%lf%lf",&node[i].price,&node[i].distance); sort(node,node+n,cmp); node[n].price=0; node[n].distance=d; if(node[0].distance>0) { printf("The maximum travel distance = 0.00\n"); } else { flag=true; nowCapacity=0.0; summ=0.0; for(int i=0; i<n;) { if(node[i+1].distance-node[i].distance>len)//两站距离大于最大行驶距离 { flag=false; printf("The maximum travel distance = %.2f\n",node[i].distance+ len); break; } minPrice=node[i].price; idx=i; for(int j=i+1; j<=n&&node[j].distance-node[i].distance<=nowCapacity*davg; ++j) {//找出当前油箱里的油能到达的所有加油站里,油价最便宜的那个 if(node[j].price<minPrice) { minPrice=node[j].price; idx=j; } } if(idx!=i) { nowCapacity-=(node[idx].distance-node[i].distance)/davg; i=idx; } else {//若找不到,找出最近的一个能到达的比当前油价便宜的站,加一些油,跑到那个站 idx=i; for(int j=i+1; j<=n&&node[j].distance-node[i].distance<=len; ++j) { if(node[j].price<node[i].price) { idx=j; break; } } if(idx!=i) { summ+=((node[idx].distance-node[i].distance)/davg-nowCapacity)*node[i].price; nowCapacity=0; i=idx; } else { //找不到比当前油站的价格还便宜的油站的时候 //在当前油站需要加满油,跑到能跑到的所有站里油价最小的那个油站 idx=i; minPrice=INF; for(int j=i+1; j<=n&&node[j].distance-node[i].distance<=len; ++j) { if(node[j].price<minPrice) { minPrice=node[j].price; idx=j; } } summ+=(cmax-nowCapacity)*node[i].price; nowCapacity=cmax-(node[idx].distance-node[i].distance)/davg; i=idx; } } } if(flag) printf("%.2f\n",summ); } return 0; }