题目描述
有了高速公路,开车从杭州到任何其他城市都很容易。但由于汽车的油箱容量有限,我们必须不时地在路上找到加油站。不同的加油站可能会给出不同的价格。你被要求仔细设计最便宜的路线去。
输入描述:
对于每个测试实例
第一行包含4个正数:Cmax(<=100),即油箱的最大容量;D(<=30000),即杭州到目的地城市的距离;Davg(<=20),即汽车每单位汽油可行驶的平均距离;N(<=500),即加油站总数。
接下来是N行,每行包含一对非负数:Pi,煤气单价,Di(<=D),这个站到杭州的距离,i=1,…N。一行中的所有数字用空格隔开。
输出描述:
对于每个测试用例,一行打印最便宜的价格,精确到小数点后2位。假设开始时油箱是空的。如果无法到达目的地,请打印“最大行驶距离=X”,其中X是车辆可以行驶的最大可能距离,精确到小数点后2位。
输入
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 50 1300 12 2
7.10 0
7.00 600
输出
749.17
贪心算法难就难在思路
- 算法一,常规的想法是从距离0开始一点一点的考虑每一步应当用什么价格的汽油,从而走完全程。这是可以的:
- 维护一个优先队列,表明现在可以用的汽油价格,每一步只需用最低价格即可,如果没有就不可行进。
- 在加油站的区间两端添加或去除可用汽油价格。
- 然而这样的做法比较麻烦。
- 算法二,如果我们换一个角度,希望用低价油,那么可以从汽油的角度。
- 用低价油走能走的部分,剩余部分则依次往高价油尝试,直至所有价格的油都被尝试过。
- 到最后如果有区间被遗漏就不能走完,否则就可以走完。
- 这样的思路就更显简洁,以下实现算法二。
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
using gas_info = pair<double, int>;
const int MAX = 30000;
double tag[MAX];
bool compare(const gas_info & x, const gas_info & y){
return x.first < y.first;
}
int main() {
int Cmax, D, Davg, N;
while (cin >> Cmax >> D >> Davg >> N) {
double p;
int d;
vector<gas_info> gas;
for(int i = 0; i < N; i++){
cin >> p >> d;
gas.emplace_back(p, d);
}
sort(gas.begin(), gas.end(), compare);
fill_n(tag, D, 0);
double cost = 0;
for(auto g : gas){
int distance = min(Cmax * Davg, D - g.second) + g.second;
for(int i = g.second; i < distance; i++){
if(tag[i] == 0){
tag[i] = 1;
cost = cost + g.first / Davg;
}
}
}
if(accumulate(tag, tag + D, 0) == D) {
cout << fixed << setprecision(2) << cost << endl;
}else {
for (int i = 0; i < D; i++) {
if (tag[i] == 0) {
cout << "The maximum travel distance = " << fixed << setprecision(2) << i * 1.0 << endl;
break;
}
}
}
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)