首先,先贴柳神的博客
想要刷好PTA,强烈推荐柳神的博客,和算法笔记
目录
题目原文
1033 To Fill or Not to Fill (25分)
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.
Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cma**x (≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; Dav**g (≤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: P**i, the unit gas price, and D**i (≤D), the distance between this station and Hangzhou, for i=1,⋯,N. All the numbers in a line are separated by a space.
Output Specification:
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.
Sample Input 1:
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
Sample Output 1:
749.17
Sample Input 2:
50 1300 12 2
7.10 0
7.00 600
Sample Output 2:
The maximum travel distance = 1200.00
题目大意
汽车从杭州出发去别的城市,路上要经过若干个加油站,这些加油站的油价是不想同的,试问,怎么加油可以让汽车的邮费最少
如果不能到达,那就输出汽车最远可以跑多少
下面都是copy柳神的
分析：贪心算法。
0.假设增加一个目的地处的加油站，距离为目的地的距离，价格为0，考虑从0距离开始能否到达最后一个加油站的问题
1.因为先开始没有油，所以如果所有的加油站距离都没有等于0的，那么说明车哪也去不了，直接输出并return
2.将加油站按照距离dis从小到大排序
3.先去第一个加油站，设置变量nowdis表示当前所在的距离，maxdis是能够到达的最大距离，nowprice是当前的站点的价格，totalPrice是总的价格。
贪心思想：
*0.寻找比自己距离远的，到能够到达的最大距离之间的加油站，看他们的油价。如果找到了更低价格的油价，就加油到刚好能到达那个加油站的距离的油，然后去那个更低价格的加油站（有更低的我一分都不想多花在别的距离上，只加到刚好满足更低价格的加油站的距离就行，那样以后的路程我就可以以更低的价格行驶啦）
1.如果找不到更低的，就找尽可能低的油价的加油站，在当前加油站加满油之后过去。因为想要让路程上使用的尽可能是低价的油，既然没有比当前更低价格的了，就让油箱加到最大值，这样能保证利益最大化，保证最大的距离使用的是便宜的油。
代码如下
下面是算法笔记里面的代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 510;
const int INF = 10000000000;
struct station {
double price, dis; //价格和与起点的距离
}st[maxn];
bool cmp(station a, station b) {
return a.dis < b.dis; //按距离从小到大排列
}
int main(void) {
int n;
double Cmax, D, Davg;
scanf("%lf%lf%lf%d", &Cmax, &D, &Davg, &n);
for (int i = 0; i < n; i++) {
scanf("%lf%lf", &st[i].price, &st[i].dis);
}
st[n].price = 0; //数组最后面放置重点,价格为0
st[n].dis = D; //终点距离为D
sort(st, st + n, cmp);//将所有的加油站按距离从小到大排序
if (st[0].dis != 0) { //如果排序后的第一个加油站距离不是0，说明无法前进
printf("The maximum travel distance = 0.00\n");
}
else {
int now = 0; //当前所处的加油站编号
//总花费,当前加油量及满油行驶距离
double ans = 0, nowTank = 0, MAX = Cmax * Davg;
while (now < n) { //每次循环将选出下一个需要到达的加油站
//选出从当前加油站满油能到达范围内的第一个油价低于当前油价的加油站
//如果没有低于当前加油站的加油站,则选择价格最低的那个
int k = -1; //最低油价的编号
double priceMin = INF; //最低油价
for (int i = now + 1; i <= n && st[i].dis - st[now].dis <= MAX; i++) {
if (st[i].price < priceMin) { //如果油价比当前最低油价地
priceMin = st[i].price; //更新最低油价
k = i;
//如果找到第一个油价低于当前油价的加油站,直接中断循环
if (priceMin < st[now].price) {
break;
}
}
}
if (k == -1)break; //满油状态下无法找到加油站,退出循环输出结果
//下面为能找到可到达的加油站k,计算转移花费
//need为从now到k需要的油量
double need = (st[k].dis - st[now].dis) / Davg;
if (priceMin < st[now].price) { //如果加油站k的油价低于当前油价
//只买足够到达加油站的油量
if (nowTank < need) { //如果当前油量不足need
ans += (need - nowTank) * st[now].price; //补足need
nowTank = 0; //到达加油站k后油量的为0
}
else {//如果当前油量超过need
nowTank -= need; //直接到达加油站k
}
}
else { //如果加油站k的油价高于当前油价
ans += (Cmax - nowTank) * st[now].price; //将邮箱加满
//到达加油站k后邮箱内油量为Cmax-need
nowTank = Cmax - need;
}
now = k; //到达加油站k，进入下一层循环
}
if (now == n) { //能到达终点
printf("%.2f\n", ans);
}
else { //不能到达终点
printf("The maximum travel distance = %.2f\n", st[now].dis + MAX);
}
}
return 0;
}
下面是柳神的代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 99999999;
struct station {
double price, dis;
};
bool cmp1(station a, station b) {
return a.dis < b.dis;
}
int main() {
double cmax, d, davg;
int n;
scanf("%lf%lf%lf%d", &cmax, &d, &davg, &n);
vector<station> sta(n + 1);
sta[0] = { 0.0, d }; //默认这个为终点,把终点放在了开始
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &sta[i].price, &sta[i].dis);
sort(sta.begin(), sta.end(), cmp1);
double nowdis = 0.0, maxdis = 0.0, nowprice = 0.0, totalPrice = 0.0, leftdis = 0.0;
if (sta[0].dis != 0) {
printf("The maximum travel distance = 0.00");
return 0;
}
else {
nowprice = sta[0].price;
}
while (nowdis < d) {
maxdis = nowdis + cmax * davg;
double minPriceDis = 0, minPrice = inf;
int flag = 0;
for (int i = 1; i <= n && sta[i].dis <= maxdis; i++) {
if (sta[i].dis <= nowdis) continue;
if (sta[i].price < nowprice) {
totalPrice += (sta[i].dis - nowdis - leftdis) * nowprice / davg;
//就加油到比自己便宜的油站
leftdis = 0.0;
nowprice = sta[i].price;
nowdis = sta[i].dis;
flag = 1;
break;
}
//油价都贵,但是要在都贵里面找最便宜的
if (sta[i].price < minPrice) {
minPrice = sta[i].price;
minPriceDis = sta[i].dis;
}
}
if (flag == 0 && minPrice != inf) { //油价都贵,我们要加满油去最便宜的加油站
totalPrice += (nowprice * (cmax - leftdis / davg));//在这个加油站要加满油
//leftdis/davg就是到达这个加油站里面,邮箱还剩余有多少油
//剩余的油可以走的里程数
//leftdis就是到达下一个加油站的时候,剩余的油还可以走多久
leftdis = cmax * davg - (minPriceDis - nowdis);
nowprice = minPrice;
nowdis = minPriceDis;
}
//如果一个都找不到的话
if (flag == 0 && minPrice == inf) {
nowdis += cmax * davg;
printf("The maximum travel distance = %.2f", nowdis);
return 0;
}
}
printf("%.2f", totalPrice);
return 0;
}
我的代码如下
半写,半抄
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
const double MaxPrice = 99999999;
using namespace std;
struct station {
double price, dis;
};
bool cmp(station a, station b) {
return a.dis < b.dis;
}
int main(void) {
double Cmax, D, Davg, N;
scanf("%lf%lf%lf%lf", &Cmax, &D, &Davg, &N);
vector<station>data(N + 1);
data[0].dis = D; data[0].price = 0.0;
for (int i = 1; i <= N; i++) {
scanf("%lf%lf", &data[i].price, &data[i].dis);
}
sort(data.begin(), data.end(), cmp);
double nowdis = 0.0, maxdis = 0.0, nowprice = 0.0, totalPrice = 0.0, leftdis = 0.0;
if (data[0].dis != 0) {
printf("The maximum travel distance = 0.00"); return 0;
}
else nowprice = data[0].price;
while (nowdis < D) {
maxdis = nowdis + Cmax * Davg;
double minPriceDis = 0, minPrice = MaxPrice;
int flag = 0;
for (int i = 1; i <= N && data[i].dis <= maxdis; i++) {
if (data[i].dis <= nowdis) continue; //一定是要找nowdis之后的啊
if (data[i].price < nowprice) {
totalPrice += ((data[i].dis - nowdis - leftdis) * nowprice / Davg);
leftdis = 0.0;
nowprice = data[i].price;
nowdis = data[i].dis;
flag = 1; //表明出现了油价更低的那个加油站
break;
}
if (data[i].price < minPrice) {
minPrice = data[i].price;
minPriceDis = data[i].dis;
}
}
if (flag == 0 && minPrice != MaxPrice) { //就是所有的加油站都比开出去的贵
totalPrice += ((Cmax - (leftdis/Davg)) * nowprice);
leftdis = Cmax*Davg-(minPriceDis-nowdis); //剩下可以走的最多的路
nowdis = minPriceDis;
nowprice = minPrice;
}
if (flag == 0 && minPrice == MaxPrice) {
nowdis += Cmax * Davg; //虽然到不到下一个加油站,但是油必须要跑完
printf("The maximum travel distance = %.2lf", nowdis);
return 0;
}
}
printf("%.2lf", totalPrice);
return 0;
}