ACM模版

描述

题解

这个贪心着实耗费了一番功夫……

首先我们设置两个标签，一个是当前加油站 pos，一个是下一个加油站 i。
此时我们选择加油站的策略如下：
当 i 是紧挨着 pos 的下一个加油站时，如果 i 单价低于 pos，则加刚好够到 i 的油；
如果 i 的单价高于 pos 时，我们先查找在 pos 处加油所能到达的所有加油站中花费低于 pos 处的第一个加油站；如果不存在，则查找所能达到的所有加油站中花费最低的加油站，加满油到达那里。

在这里我将起点置为0号加油站，终点置为 N + 1 号加油站，这时我们在进行上述判断时，需要格外注意一点，当从某一个站可以直接到达终点站时，要特别考虑是否直达并且加刚好够用的油。上述的情况出现在 pos 站和终点站之间没有任何一站的花费比 pos 站低的时候。

这个题的关键还是细心与 debug，如果对 IDE 不熟悉，debug 起来将是一个繁琐至极的事情……

代码

#include <iostream>

using namespace std;

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

int N;
double DD1, C, DD2, PP;
double D[MAXN], P[MAXN];

int main(int argc, const char * argv[])
{
    cin >> DD1 >> C >> DD2 >> PP >> N;
    D[0] = 0;
    P[0] = PP;
    for (int i = 1; i <= N; i++)
    {
        cin >> D[i] >> P[i];
    }
    N++;
    D[N] = DD1;
    P[N] = INF;

    double cost = 0, state = 0;
    int max_len = C * DD2, pos = 0;
    for (int i = 1; i <= N; i++)
    {
        if (P[i] < P[pos] && (D[i] - D[pos]) <= max_len)
        {
            cost += ((D[i] - D[pos]) / DD2 - state) * P[pos];
            pos = i;
            state = 0;
        }
        else if (P[i] >= P[pos] && (D[i] - D[pos]) <= max_len)
        {
            int tag = -1;
            double p = P[pos];
            for (int j = pos + 1; j <= N && (D[j] - D[pos]) <= max_len; j++)
            {
                if (P[j] < p)
                {
                    tag = j;
                    break;
                }
            }
            if (tag == -1 && (D[N] - D[pos]) <= max_len)
            {
                cost += ((D[N] - D[pos]) / DD2 - state) * P[pos];
                pos = N;
                i = N;
                state = 0;
            }
            if (tag != -1)
            {
                cost += ((D[tag] - D[pos]) / DD2 - state) * P[pos];
                pos = tag;
                i = tag;
                state = 0;
            }
            else
            {
                int tag = -1;
                double p = INF + 10;
                for (int j = pos + 1; j <= N && (D[j] - D[pos]) <= max_len; j++)
                {
                    if (P[j] < p)
                    {
                        tag = j;
                        p = P[j];
                    }
                }
                if (tag != -1)
                {
                    cost += (C - state) * P[pos];
                    state = C - (D[tag] - D[pos]) / DD2;
                    pos = tag;
                    i = tag;
                }
            }
        }
    }

    if (pos == N)
    {
        printf("%.2f\n", cost);
    }
    else
    {
        cout << "No Solution\n";
    }

    return 0;
}