题目地址:http://pat.zju.edu.cn/contests/pat-a-practise/1033

此题是一道贪心算法题,难度较大,关键在于贪心策略的选择:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std; struct GasStation
{
double price;
double distance;
bool operator<(const GasStation& rhs) const
{
return distance<rhs.distance;
}
}; vector<GasStation> gasStations;
int _tmain(int argc, _TCHAR* argv[])
{
double Cmax,D,Davg;
int N;
scanf("%lf %lf %lf %d",&Cmax,&D,&Davg,&N);
GasStation station;
int i;
for(i=;i<N;++i)
{
scanf("%lf %lf",&station.price,&station.distance);
gasStations.push_back(station);
}
//将目的地当做最后一个加油站,距离为D,价格为0,以便贪心选择时总是朝着目的地前进
station.distance=D;
station.price=;
gasStations.push_back(station);
sort(gasStations.begin(),gasStations.end());
if(gasStations[].distance>)
{
printf("The maximum travel distance = 0.00\n");
return ;
}
double curGas=0.0,minSpend=0.0,minPrice;
const double driveLimit=Cmax*Davg;
int j,pivot;
for(i=;i<N;) //在前N个加油站都有可能加油
{
if(gasStations[i+].distance-gasStations[i].distance>driveLimit)
{
printf("The maximum travel distance = %.2lf\n",gasStations[i].distance+driveLimit);
return ;
}
pivot=i;
minPrice=gasStations[i].price;
//如果有油,找到不加油就能开到的比当前加油站便宜的加油站,直接开到那里加油
double curDis=curGas*Davg;
for(j = i+;j<=N && gasStations[j].distance-gasStations[i].distance <= curDis;++j)
{
if(gasStations[j].price<minPrice)
{
minPrice=gasStations[j].price;
pivot=j;
}
}
if(pivot!=i)
{
curGas-=(gasStations[pivot].distance-gasStations[i].distance)/Davg;
i=pivot;
continue;
} //以当前邮箱里面的油能跑到的范围内没有比当前加油站更便宜的加油站,于是在当前加油站后跑到第一个比当前
//加油站便宜的加油站
for(j=i+;j<=N && gasStations[j].distance-gasStations[i].distance <= driveLimit;++j)
{
if(gasStations[j].price<minPrice)
{
pivot=j;
break;
}
}
if(pivot!=i)
{
minSpend+=((gasStations[pivot].distance-gasStations[i].distance)/Davg-curGas)*gasStations[i].price;
i=pivot;
curGas=;
continue;
} //就算加满油后也不能跑到一个比当前加油站更便宜的加油站,则在加满油后跑到能跑到的加油站里面最便宜的一个
minPrice=INT_MAX;
for(j=i+;j<=N && gasStations[j].distance-gasStations[i].distance<=driveLimit;++j)
{
if(gasStations[j].price<minPrice)
{
minPrice=gasStations[j].price;
pivot=j;
}
}
minSpend+=(Cmax-curGas)*gasStations[i].price;
curGas=Cmax-(gasStations[pivot].distance-gasStations[i].distance)/Davg;
i=pivot;
}
printf("%.2lf\n",minSpend); return ;
}

最新文章

  1. C#基础篇 - 正则表达式入门
  2. 设计模式之工厂模式VS抽象工厂
  3. Redis学习笔记7--Redis管道(pipeline)
  4. html5 请求的URL转成 OC可用属性字符串显示
  5. 前端学习 第二弹: JavaScript中的一些函数与对象(1)
  6. &lt;meta&gt;元素
  7. Fresco
  8. 黄聪:禁止wordpress版本自动升级的解决方案
  9. Constant is not finite! That&#39;s illegal. constant:inf&#39;
  10. jquery正则常用的
  11. 自然语言处理之jieba分词
  12. jmeter常用组件
  13. iis支持asp.net4.0的注册命令使用方法
  14. 解决 winform 界面对不齐
  15. AndroidA——背景选择器selector用法汇总(一)
  16. 函数式编程--响应式编程 ---android应用例子
  17. Standard Java集合类问题待整理
  18. Contiki进程间的交互
  19. js插件设置innerHTML时,在IE8下报错“未知运行时错误”
  20. 选择器 nth-child和 nth-of-type的区别

热门文章

  1. 正确配置jstl的maven依赖,jar包冲突的问题终于解决啦
  2. A Full Hardware Guide to Deep Learning
  3. PHP mysql_real_escape_string() 函数
  4. About GAC
  5. SpringMVC可以配置多个拦截后缀*.html和.do等
  6. RxJava开发精要4 – Observables过滤
  7. 我的第一个Spring程序
  8. Hadoop家族学习路线图
  9. oracle删除列
  10. apache开源项目--kafka