PAT甲级1033. To Fill or Not to Fill
题意：
有了高速公路，从杭州到任何其他城市开车很容易。但由于一辆汽车的坦克容量有限，我们不得不在不时地找到加油站。不同的加油站可能会给不同的价格。您被要求仔细设计最便宜的路线。
输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行包含4个正数：Cmax（<= 100），坦克的最大容量; D（<= 30000），杭州与目的地城市的距离; Davg（<= 20），汽车可以运行的单位气体的平均距离;和N（<= 500），加油站总数。
随后N行，每个包含一对非负数：Pi，单位气体价格，Di（<= D），本站与杭州之间的距离，i = 1，... N。一行中的所有数字都以空格分隔。
输出规格：
对于每个测试用例，打印一行中最便宜的价格，精确到2位小数。
假设坦克在开始时是空的。如果不可能到达目的地，请打印“最大行驶距离= X”，其中X是汽车可以运行的最大可能距离，精确到2位小数。
思路：
贪心。
- 结果保留两位小数
- 第一个加油站必须在0
//最后一站。判断是否能到达destination。
//非最后一战。向后搜索maxlen内第一个便宜或者等价的station
//有的话，停止搜索，买刚好用完的汽油。并且以这个station为下一个站台continue
//没有的话，判断能否到达destination。
//能到达destination，买刚好用完的汽油去destination，break
//不能的话，买满汽油，去价格最便宜的一个station作为下一个站台。
ac代码：
C++
// pat1033.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<stdio.h>
#include<unordered_map>
using namespace std;
//cheapest prices or max_distance 小数点后两位
//station[0].dis 必须等于 0 ;
struct sta
{
double dis;
double price;
};
int capacity, destination, d_avg, nums; //100, 3e5, 20 , 500
sta station[505];
bool stacmp(sta& a, sta& b)
{
return a.dis < b.dis;
}
int main()
{
cin >> capacity >> destination >> d_avg >> nums;
int maxlen = d_avg * capacity;
for(int i = 0; i < nums; i++)
{
cin >> station[i].price >> station[i].dis;
}
sort(station, station + nums,stacmp);
int cur = 0;
double res = 0,extra = 0,maxdis = 0;
while (station[0].dis == 0 && cur < nums)
{
//cout << "当前station： " << cur << endl;
//最后一站。判断是否能到达destination。
//非最后一战。向后搜索maxlen内第一个便宜或者等价的station
//有的话，停止搜索，买刚好用完的汽油。并且以这个station为下一个站台continue
//没有的话，判断能否到达destination。
//能到达destination，买刚好用完的汽油去destination，break
//不能的话，买满汽油，去价格最便宜的一个station作为下一个站台。
if (cur == nums - 1)
{
if (station[cur].dis + maxlen >= destination)
{
res += ((destination - station[cur].dis) / d_avg - extra) * station[cur].price;
extra = 0;
break;
}
else
{
res = 0;
maxdis = station[cur].dis + maxlen;
break;
}
}
int next = cur + 1, minindex = cur + 1;
double minst = station[cur + 1].price;
bool flag = false;
while (next < nums && station[cur].dis + maxlen >= station[next].dis)
{
if (station[next].price <= station[cur].price)
{
res += ((station[next].dis - station[cur].dis) / d_avg - extra) * station[cur].price;
//cout << res << endl;
extra = 0;
flag = true;
cur = next;
break;
}
if (station[next].price < minst)
{
minst = station[next].price;
minindex = next;
}
next++;
}
if (flag) continue;
if (station[cur].dis + maxlen >= destination)
{
res += ((destination - station[cur].dis) / d_avg - extra) * station[cur].price;
//cout << res << endl;
extra = 0;
break;
}
else
{
res += (capacity - extra) * station[cur].price;
extra = capacity - (station[minindex].dis - station[cur].dis) / d_avg;
//cout << res << endl;
cur = minindex;
}
}
if (res == 0) printf("The maximum travel distance = %.2f\n", maxdis);
else printf("%.2f\n", res);
return 0;
}