锣鼓P1016（旅行者预算）
问题描述
旅行者希望以最小的成本驾驶汽车从一个城市到另一个城市（假设启动时油箱是空的）。给定两个城市之间的距离 D1、汽车油箱容量 C（升）、每升汽油可行驶的距离 D2、起点 PP 处每升汽油的价格以及加油站数量沿途N（N可以为零），加油站ii到起点的距离Di，每升汽油价格Pi（i=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No”。
输入格式
第一行，D1、C、D2、P、N
接下来有N行。
第i 1行，两个数字，第i个加油站到起点的距离Di和每升汽油的价格Pi。
输出格式
所需的最低费用，四舍五入到小数点后两位。如果无法到达目的地，则输出“No”。
解决问题的思路
这个问题问得有点麻烦。本来想用滚动阵列，就像P1004一样，但是有一个问题，涉及到车内的油量。如果前面的油没有用完，会影响后面的成本。换句话说，它们不是独立的问题，而是相互关联的。
但我们可以结合实际来考虑这个问题。现实生活中，如果我们长途旅行，如果汽车油箱里的油都用完也无法到达两个加油站之间的距离，那么我们只能输出“No”，表示没有任何东西可以做到，但我们确实无法到达那里。那么即使到了那里，我们还是要考虑成本。毕竟我们省下来的钱可以用来买很多好吃的。这里我们可以知道C*D2就是我们的到达范围。如果附近有一个加油站比我们现在所在的加油站便宜，那么只要到达那个加油站就可以了，因为我们可以在剩下的路程中使用更便宜的汽油。如果碰巧，我们能到达的范围内的油价都比我们当前所在加油站的油价贵，那么我们就加油，选择那些昂贵的加油站中最便宜的加油站作为下次加油观点。我们一路前行，终于到达了目的地城市。这个时候油箱里应该已经没有汽油了，这说明我们花的钱刚刚好。
因为这些题是我自学的，所以我不知道如何实际判断正确性。但请注意，本题测试点的答案是 0，位于 0.01 位置。我在第一次输出时没有输出这个0，结果是WA。是的，还是太年轻了。
很便宜，给你看我的代码。
代码
#include #include using namespace std; double d1; double c; double d2; double p; int n; double pi[8]; double di[8]; double cost; int main() { cin >> d1 >> c >> d2 >> p >> n;
double h = 0;//汽车油量 for (int i = 1;i <= n;i ) { cin >> di[i] >> pi[i]; } pi[0] = p; di[n 1] = d1; for (int i = (n 1) ;i > 0;i--) { di[i] -= di[i - 1]; if (di[i] > (c * d2)) { cout << "No Solution" << endl; return 0; } } int flag = 0;//汽车到的位置 while (flag != (n 1)) { int i = flag 1; double len = 0; double minp = 500; int pmin = i; while ((len di[i]) <= (c*d2)) { len = di[i]; if (pi[i] < minp) { minp = pi[i]; pmin = i; if (pi[i] <= pi[flag]) { break; } } i ; } if (minp <= pi[flag]) { cost = ((len / d2) - h)*pi[flag]; h = 0; } else { cost = (c - h)*pi[flag]; h = c - len / d2; } flag = pmin; } cout << setprecision(2) << fixed << cost << endl; return 0; }
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
