Codeforces 883D. Packmen Strike Back

题意：

在$1 \times n$的地图上有一些吃豆人和豆子，你可以决定每个吃豆人行走的方向，使他们吃到尽可能多的豆子，并在这个基础上最小化用时。吃豆人同时出发。

题解：

首先，如果有至少两个吃豆人，那么所有豆子都可以吃到，只有一个就只能吃半边。然后二分时间。怎么check呢？设$f_{i, 0/1}$表示前$i$个吃豆人，第$i$个往左走/往右走，不能吃到的最靠左的豆子的位置。$f_{i, 1}$的转移就是看一下$i$能不能覆盖$f_{i - 1}$。具体细节想想就出来了。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#define pa pair<int, int>
using namespace std;

const int inf = 0x3f3f3f3f;
int n, p[1000010], sum[1000010], cnt = 0, f[1000010][2], r[1000010];
char s[1000010];

bool chk(int x)
{
    // printf("%d\n", x);
    f[0][0] = f[0][1] = r[0];
    for (int i = 1; i <= cnt; i++)
    {
        f[i][1] = max(f[i - 1][0], f[i - 1][1]) >= p[i] ? r[min(n + 1, p[i] + x + 1)] : max(f[i - 1][0], f[i - 1][1]);
        f[i][0] = r[0];
        if (f[i - 1][0] >= p[i] - x) f[i][0] = max({f[i][0], f[i - 1][0], r[p[i] + 1]});
        else f[i][0] = max(f[i][0], f[i - 1][0]);
        if (f[i - 1][1] >= p[i] - x) f[i][0] = max(f[i][0], r[min(n + 1, max({0, p[i - 1] + x + 1, p[i] + 1}))]);
        else f[i][0] = max(f[i][0], f[i - 1][1]);
        // printf("%d %d\n", f[i][0], f[i][1]);
    }
    return max(f[cnt][0], f[cnt][1]) == n + 1;
}
int main()
{
    scanf("%d%s", &n, s + 1);
    p[0] = -inf;
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1];
        if (s[i] == 'P') p[++cnt] = i;
        else if (s[i] == '*') sum[i]++;
    }/*
    for (int i = 1; i <= n; i++)
        printf("%d ", sum[i]);
    puts("");*/
    r[n + 1] = n + 1;
    for (int i = n; i >= 0; i--)
        if (s[i] == '*')
            r[i] = i;
        else
            r[i] = r[i + 1];
    if (cnt == 1)
    {
        int l = 1, r = n;
        while (s[l] != '*') l++;
        while (s[r] != '*') r--;
        pa ans = max(make_pair(sum[p[1] - 1], l - p[1]), make_pair(sum[n] - sum[p[1]], p[1] - r));
        printf("%d %d\n", ans.first, -ans.second);
        return 0;
    }
    printf("%d ", sum[n]);
    int l = 1, len = n;
    while (len)
    {
        int md = l + (len >> 1);
        if (!chk(md))
        {
            l = md + 1;
            len = len - (len >> 1) - 1;
        }
        else
            len >>= 1;
    }
    printf("%d\n", l);
}