526互联

洛谷 P1081 题解

发布时间 2023-07-02 18:59:47作者: yuhang-ren

P1081 [NOIP2012 提高组] 开车旅行 题解

洛谷题目链接

Solution

首先考虑这道题的暴力做法，对于第一问，枚举每个起始点，暴力计算每个点之后最近和第二近的位置，计算答案，最后取最大值。对于第二问，对每个询问独立模拟即可。复杂度较高，无法通过此题。

第一个优化： 考虑到对于固定的当前点和当前驾驶者，接下来的路径是一定的，可以利用倍增来处理。

第二个优化： 可以利用 set 预处理出每个点之后最近和第二近的节点、到达下一个节点的距离。注意需要逆序插入点。如果不希望用如此多的迭代器操作也可以手写平衡树。复杂度为 \(O(n \log n)\)

预处理部分代码如下，\(dp_{i,j,k}\) 表示 \(k\) 从点 \(j\) 继续走 \(2^i\) 次到达的点。
\(disa_{i,j,k}\) 表示 \(k\) 从点 \(j\) 继续走 \(2^i\) 次小 A 行驶的距离。\(disb_{i,j,k}\) 表示 \(k\) 从点 \(j\) 继续走 \(2^i\) 次小 B 行驶的距离。

其中 \(k = 1\) 为小 A， \(k = 2\) 为小 B。

for (int i = n; i; i--)
{
    st.insert({h[i], i});//插入当前点
    auto pos = st.lower_bound({h[i], i});
    --pos;
    // 更小的第一个 位置 / 距离
    int li = pos->second, lh = pos->first;
    ++pos;
    ++pos;
    // 更大的第一个 位置 / 距离
    int nx = pos->second, nh = pos->first;
    --pos;
    int pa, pb;

    // 小的更近
    if (abs(nh - h[i]) >= abs(h[i] - lh))
    {
        pb = li;
        --pos;
        --pos;
        // 第二小的和大的比较
        if (abs(nh - h[i]) >= abs(h[i] - pos->first))
        {
            pa = pos->second;
        }
        else
        {
            pa = nx;
        }
    }
    else //大的更近
    {
        pb = nx;
        ++pos;
        ++pos;
        // 第二大和小的比较
        if (abs(pos->first - h[i]) >= abs(h[i] - lh))
        {
            pa = li;
        }
        else
        {
            pa = pos->second;
        }
    }
    dp[0][i][0] = pa;
    dp[0][i][1] = pb;
    disa[0][i][0] = abs(h[i] - h[pa]);
    disb[0][i][1] = abs(h[i] - h[pb]);
}

接下来处理出所有值，需要注意的是 \(2^0 = 1\) 为奇数，结束时开车的人会改变，需要特判。

for (int i = 1; i <= 18; i++)
{
    for (int j = 1; j <= n; j++)
    {
        for (int k = 0; k <= 1; k++)
        {
            if (i == 1)
            {
                dp[1][j][k] = dp[0][dp[0][j][k]][1 - k];
                disa[1][j][k] = disa[0][j][k] + disa[0][dp[0][j][k]][1 - k];
                disb[1][j][k] = disb[0][j][k] + disb[0][dp[0][j][k]][1 - k];
            }
            else
            {
                dp[i][j][k] = dp[i - 1][dp[i - 1][j][k]][k];
                disa[i][j][k] = disa[i - 1][j][k] + disa[i - 1][dp[i - 1][j][k]][k];
                disb[i][j][k] = disb[i - 1][j][k] + disb[i - 1][dp[i - 1][j][k]][k];
            }
            // cout << "disa[" << i << "][" << j << "][" << k << "]=" << disa[i][j][k] << endl;
            // cout << disa[1][1][0] << endl;
        }
    }
}

求对于给定的 \(x\) 和 \(s\) 两人分别走的距离，很典型的倍增套路。

void solution(int ss, int xx)
{
    int now = ss;
    la = lb = 0;
    for (int i = 18; ~i; i--)
    {
        if (dp[i][now][0] && la + lb + disa[i][now][0] + disb[i][now][0] <= xx)
        {
            la += disa[i][now][0];
            lb += disb[i][now][0];
            now = dp[i][now][0];
        }
    }
}

回答第一问：枚举起点，取最小值。

double ans = 2010000000.000;
int ansid = 0;
for (int i = 1; i <= n; i++)
{
    solution(i, x0);
    double ans__ = (double)la / (double)(lb);
    if (ans__ < ans)
    {
        ans = ans__;
        ansid = i;
    }
    else if (ans__ == ans && h[ansid] < h[i])
    {
        ansid = i;
    }
}
writeln(ansid);

回答第二问：直接调用函数。

for (int i = 1; i <= m; i++)
{
    solution(querys[i].first, querys[i].second);
    writesp(la), writeln(lb);
}

Codes

#include <bits/stdc++.h>
using namespace std;
#define max_n 110101
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
    {
        write_(x / 10);
    }
    putchar(x % 10 + '0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
int n, h[max_n], x0, m;
set<pair<int, int>> st;
pair<int, int> querys[max_n];
int dp[19][max_n][3];
int disa[19][max_n][3];
int disb[19][max_n][3];
int la, lb;
void solution(int ss, int xx)
{
    int now = ss;
    la = lb = 0;
    for (int i = 18; ~i; i--)
    {
        if (dp[i][now][0] && la + lb + disa[i][now][0] + disb[i][now][0] <= xx)
        {
            // cout << i << " " << now << " " << disa[1][1][0] << endl;
            la += disa[i][now][0];
            lb += disb[i][now][0];
            now = dp[i][now][0];
        }
    }
    // cout << "#" << la << " " << lb << endl;
}
signed main()
{
#if _clang_
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    read(n);
    for (int i = 1; i <= n; i++)
    {
        read(h[i]);
    }
    read(x0), read(m);
    for (int i = 1; i <= m; i++)
    {
        read(querys[i].first);
        read(querys[i].second);
    }
    h[0] = 2000000000;
    h[n + 1] = -2000000000;
    st.insert({h[0], 0});
    st.insert({h[n + 1], n + 1});
    for (int i = n; i; i--)
    {
        st.insert({h[i], i});
        auto pos = st.lower_bound({h[i], i});
        --pos;
        int li = pos->second, lh = pos->first;
        ++pos;
        ++pos;
        int nx = pos->second, nh = pos->first;
        --pos;
        int pa, pb;
        //   cout << "@" << li << " " << lh << " " << nx << " " << nh << endl;
        if (abs(nh - h[i]) >= abs(h[i] - lh))
        {
            //   cout << "A" << endl;
            pb = li;
            --pos;
            --pos;
            if (abs(nh - h[i]) >= abs(h[i] - pos->first))
            {
                pa = pos->second;
            }
            else
            {
                pa = nx;
            }
        }
        else
        {
            // cout << "B" << endl;
            pb = nx;
            ++pos;
            ++pos;
            if (abs(pos->first - h[i]) >= abs(h[i] - lh))
            {
                pa = li;
            }
            else
            {
                pa = pos->second;
            }
        }
        dp[0][i][0] = pa;
        dp[0][i][1] = pb;
        disa[0][i][0] = abs(h[i] - h[pa]);
        disb[0][i][1] = abs(h[i] - h[pb]);
        //  cout << dp[0][i][0] << " " << dp[0][i][1] << " " << disa[0][i][0] << " " << disb[0][i][1] << endl;
    }
    for (int i = 1; i <= 18; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 0; k <= 1; k++)
            {
                if (i == 1)
                {
                    dp[1][j][k] = dp[0][dp[0][j][k]][1 - k];
                    disa[1][j][k] = disa[0][j][k] + disa[0][dp[0][j][k]][1 - k];
                    disb[1][j][k] = disb[0][j][k] + disb[0][dp[0][j][k]][1 - k];
                }
                else
                {
                    dp[i][j][k] = dp[i - 1][dp[i - 1][j][k]][k];
                    disa[i][j][k] = disa[i - 1][j][k] + disa[i - 1][dp[i - 1][j][k]][k];
                    disb[i][j][k] = disb[i - 1][j][k] + disb[i - 1][dp[i - 1][j][k]][k];
                }
                // cout << "disa[" << i << "][" << j << "][" << k << "]=" << disa[i][j][k] << endl;
                // cout << disa[1][1][0] << endl;
            }
        }
    }
    double ans = 2010000000.000;
    int ansid = 0;
    for (int i = 1; i <= n; i++)
    {
        solution(i, x0);
        // cout << la << " " << lb << endl;
        double ans__ = (double)la / (double)(lb);
        if (ans__ < ans)
        {
            ans = ans__;
            ansid = i;
        }
        else if (ans__ == ans && h[ansid] < h[i])
        {
            ansid = i;
        }
    }
    writeln(ansid);
    for (int i = 1; i <= m; i++)
    {
        solution(querys[i].first, querys[i].second);
        writesp(la), writeln(lb);
    }
    return 0;
}