• 奇怪的东西

  • WA了两小时
  • 比rk2快一倍,但代码长4倍
  • 请思考本题用dp怎么做

• 题意

  今有一区间,人,物具陈其上,间或亦有空.其人可左右徙于上.求让人的移动轨迹覆盖所有物品的情况下,人移动的路程的最大值的最小值.

• 题解

  根据题意,显然看出是二分.再考虑一个人的走法:

  • 向左走,不回头

  • 向右走,不回头

  • 向左再向右,左边重复走

  • 向右再向左,右边重复走

若我们从左到右把人扫一遍,必然要保证先把左边的没走到的物品走到,同时在还有步数的情况下向右走.

这样会WA on #7 ,原因在于先向右走再向左走到第一个没走到的物品可能更优,因为重复的部分可能更少.

考虑分类讨论:用一个物品指针指向还没走到的最靠左的物品

1. 步数不够到达最左边的没走到的物品\(\to\)直接return false

2. 步数只能到最左边的物品,无法向右走\(\to\)把物品指针向右更新到人右边

3. 步数很充足\(\to\)在3,4两种走法中取最优解

4. 指针在人右边\(\to\)把物品指针尽可能向右更新

结束后判断指针是否大于\(Cnt_{package}\)即可

这样就又WA了,原因在于二分的右边界应当是\(\frac{3n}{2}\),即只有一个人在正中间,先向某方向然后再折返的答案,程序里为了简单写成了\(2n\).

最终复杂度:\(O(Cnt_{people}\log2n)\),明显快于\(O(n\log2n)\).

• 代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100005;
int n, L, R, cnt1, cnt2;
int peo[N], pack[N];
string s;
bool check(int k)
{
    int await_pick = 1;
    for (int i = 1; i <= cnt1; i++)
    {
        int start_pos = await_pick;
        if (await_pick > cnt2)
            return true;
        if (pack[start_pos] < peo[i])
        {
            if (pack[start_pos] < peo[i] - k)//第一种情况
                return false;
            if (k <= peo[i] - pack[start_pos] + 1)//第二种情况
            {
                while (pack[await_pick + 1] <= peo[i] && await_pick <= cnt2 && pack[await_pick + 1] <= peo[i + 1])
                    await_pick++;
                if (pack[await_pick] <= peo[i] && pack[await_pick] <= peo[i + 1])
                    await_pick++;
            }
            else
            {
                if (k > (2 * (peo[i] - pack[start_pos])))
                {//第三种情况,先向左走
                    int temp = k - (2 * (peo[i] - pack[start_pos]));
                    while (pack[await_pick + 1] <= peo[i] + temp && await_pick <= cnt2 && pack[await_pick + 1] <= peo[i + 1])
                        await_pick++;
                    if (pack[await_pick] <= peo[i] + temp && pack[await_pick] <= peo[i + 1])
                        await_pick++;
                }
                if (peo[i] + (k + pack[start_pos] - peo[i]) / 2 >= pack[await_pick])
                {//第三种情况,先向右走
                    int temp = (k + pack[start_pos] - peo[i]) / 2;
                    while (pack[await_pick + 1] <= peo[i] + temp && await_pick <= cnt2 && pack[await_pick + 1] <= peo[i + 1])
                        await_pick++;
                    if (pack[await_pick] <= peo[i] + temp && pack[await_pick] <= peo[i + 1])
                        await_pick++;
                }
            }
        }
        else
        {//第四种情况
            while (pack[await_pick + 1] <= peo[i] + k && await_pick <= cnt2 && pack[await_pick + 1] <= peo[i + 1])
                await_pick++;
            if (pack[await_pick] <= peo[i] + k && await_pick <= cnt2 && pack[await_pick] <= peo[i + 1])
                await_pick++;
        }
    }
    if (await_pick > cnt2)
        return true;
    else
        return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> s;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'P')
            peo[++cnt1] = i + 1;
        if (s[i] == '*')
            pack[++cnt2] = i + 1;
    }
    peo[cnt1 + 1] = 0x7fffffff;
    pack[cnt2 + 1] = 0x7fffffff;
    L = 1, R = 2 * n;//注意二分边界
    while (L <= R)
    {
        int mid = (L + R) / 2;
        if (check(mid))
            R = mid - 1;
        else
            L = mid + 1;
    }
    cout << L;
}