Noip 1999 / P1016 旅行家的预算
这是一道贪心 + 模拟的题。
贪心思路比较好想，很考验模拟功底。难点在于需要维护的东西很多。
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市，途中有N个加油站，有选择性地加油。若能到达目的地，输出最少费用；反之，输出“No Solution”。
样例输入
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
样例输出
26.95
我们可以定义一个结构体来储存，第i个加油站与起点的距离，和每升油的价钱（不定义也没事，也就用2或3个数组而已）
const int size = 505;
struct T {
int index;
double p, f;
} a[size];
首先，因为最开始油箱是空的（题目给出了的），所以在起点必须加油，然后我们需要思考的是加多少油，也就是思考这道题的贪心策略————怎么加油使得费用最少。
我们还要思考的是什么时候输出“No Solution”。举个例子:
input：10 2 1 5 2
5 10
6 7
分析一下数据：油箱最大容量是2升，每升最多行驶距离为1，所以我们可以算出一次加油后最多能行驶的距离为2。
而第一个加油站与起点的距离为5，即使在起点加满油也无法到达第一个加油站，所以旅行失败，输出”No Solution“。
之后也是同理，设加满油能行驶的最大距离为，只要的都是无解的。
可以在输入时预处理，筛出失败的，如下
a[0].f = 0;
for (int i = 1; i <= N; i++) {
scanf("%lf %lf", &a[i].f, &a[i].p);
if (a[i].f - a[i - 1].f > C * D) { //C * D为加满油行驶的最大距离
printf("No Solution");
return 0;
}
}
要想费用最少，不难想到在油价最便宜的加油站加油。但仅仅这样范围太大了，但我们由上一种情况可知，可选的加油站距离起点的距离肯定在a[i].f ~ a[i].f + C * D之间。
这里又需要分两种情况：1.在区间内有油价低于当前油价的加油站；2.没有油价低于当前油价的加油站。
若有，且剩余油量无法到达该加油站，则在当前加油站加油，加到恰好能到达该加油站的油量即可;否则，就直接去到该加油站。
若没有，则在当前加油站加满油，开到此区间中油价最便宜的加油站再做这样的考虑。最重要的一点是，在这种情况中还要判断，如果当前加油站与目的地距离小于等于C * D，就可
加油至刚好到目的地的油量。
题目中还提示了你可能还会有N为0的毒瘤存在，因此我试了试，我这个想法在N为0时可能没有输出，所以要特判一下。
在我的程序里，需要维护的东西有4个：1.费用（必须的啊）；2.所处加油站的编号；3.已经行驶的距离；4.剩下的油量。
于是我便开始了我的的尝试：
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
const int size = 505;
struct T {
double p, f;
} a[size];
int N, last, in_min;
double F, C, D, P, res, now, Min, Y, Sum;
int main() {
scanf("%lf %lf %lf %lf %d", &F, &C, &D, &P, &N);
a[0].f = 0, a[0].p = P;
res = C * D, now = 0, last = 0, Min = INT_MAX;
if (!N) {
if (res < F) {
printf("No solution");
return 0;
} else {
printf("%.2lf", F / D * P);
return 0;
}
}
for (int i = 1; i <= N; i++) {
scanf("%lf %lf", &a[i].f, &a[i].p);
if (a[i].f - a[i - 1].f > res) {
printf("No solution");
return 0;
}
}
while (now <= F) {
for (int i = last + 1; i <= N && a[i].f - a[last].f <= res; i++) {
if (a[i].p < Min) {
Min = a[i].p;
in_min = i;
}
}
double temp = (a[in_min].f - a[last].f) / D;
if (Min < a[last].p) {
if (temp <= Y) {
Y -= temp;
} else {
Sum += (temp - Y) * a[last].p;
Y = 0;
}
} else {
if (F - now <= res) {
Sum += ((F - now) / D - Y) * a[last].p;
break;
}
Sum += (C - Y) * a[last].p;
Y = C - temp;
}
Min = INT_MAX;
last = in_min;
now = a[in_min].f;
}
printf("%.2lf", Sum);
return 0;
}
虽然这段代码已经能A了，但是这并不是正解，还有bug——问题出在区间内有油价低于当前油价的加油站这种情况。
我的策略中是在区间中找到最便宜的，
然后直接抵达该加油站。但是只需要在区间中遇到比当前便宜的就可以停止了，这比直接到最便宜的加油站省钱，举个例子：
input:3 4 1 3 2
1 1 2
2 2 1
-
按照开始的贪心策略，直接到达区间内最便宜的，在此样例中就是2号加油站，算下来总费用
-
按照改进后的思路，即先到1号，再到2号，最后到目的地，总费用
综合起来，发现第2种才是最优解~
加上这一步，才算是正解
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
const int size = 505;
struct T {
double p, f;
} a[size];
int N, last, in_min;
double F, C, D, P, res, now, Min, Y, Sum;
int main() {
scanf("%lf %lf %lf %lf %d", &F, &C, &D, &P, &N);
//F表示目的地与起点的距离
//C最大容油量，D每升油可驶距离，P起点加油站的油价
a[0].f = 0, a[0].p = P;
res = C * D, now = 0, last = 0, Min = INT_MAX;
if (!N) { //N为0时的特判
if (res < F) {
printf("No solution");
return 0;
} else {
printf("%.2lf", F / D * P);
return 0;
}
}
for (int i = 1; i <= N; i++) {
scanf("%lf %lf", &a[i].f, &a[i].p);
if (a[i].f - a[i - 1].f > res) { //无解的判断
printf("No Solution");
return 0;
}
}
while (now <= F) {
for (int i = last + 1; i <= N && a[i].f - a[last].f <= res; i++) {
//找区间内最小的
if (a[i].p < Min) {
Min = a[i].p;
in_min = i;
if (Min < a[last].p)
break;
}
}
double temp = (a[in_min].f - a[last].f) / D;
//需要temp升的油可恰好到该加油站
if (Min < a[last].p) {
if (temp <= Y) {
Y -= temp; //剩油更新
} else {
Sum += (temp - Y) * a[last].p;
Y = 0; //剩油更新
}
} else {
if (F - now <= res) { //可直接到终点
Sum += ((F - now) / D - Y) * a[last].p;
break;
}
Sum += (C - Y) * a[last].p;
Y = C - temp; //剩油更新
}
Min = INT_MAX; //将Min更新
last = in_min; //更新所处加油站的编号
now = a[in_min].f; //更已行驶的距离
}
printf("%.2lf", Sum);
return 0;
}
弱弱地说一句，可能某谷的数据还是有点水
下一篇： Docker部署RabbitMQ集群