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