题解：AT_joisc2017_c 手持ち花火 (Sparklers)

· · 题解

AT_joisc2017_c 手持ち花火

前言

今典的拓拓拓拓展题

校内模拟赛搬了这道题，来写个题解。

正文

最优的方法是所有人朝着 k 走，与 k 相遇时就一起走，当 k 的火把熄灭时再把其他同位置的一个火把点燃，相当于每个火把加了 t 秒的总燃烧时间。因为所有人速度一样，因此相对位置不会变，即 i<j<k 时，若 i 能被点燃，那 j 也一定会被点燃过，右侧同理。得出可点燃的火把一定是一个区间 [l,r](l\le k\le r)。

接下来求区间 [l,r] 能否能拓展至 [l-1,r] 或 [l,r+1]。首先考虑 [l,r] 是否合法，若全都能点燃，其总燃烧时长为 t(r-l) 秒（最后一个点燃后直接结束），而所有的人聚在一起的时间即为 l 与 r 相遇的时间（所有人的相对位置不变），即 \dfrac{x_r-x_l}{2v}。得到不等式 t(r-l)\ge \dfrac{x_r-x_l}{2v}，当满足该不等式时，区间 [l,r] 是合法的。

继续拆解不等式，得到 2vtr-x_r\ge 2vtl-x_l。

发现 v 具有单调性（若 v 可行则 v+1 也可行），因此考虑二分。于是问题就变成了给定一个非负整数 v，初始 l=r=k，每次可以 l\leftarrow l-1 或 r\leftarrow r+1，且需满足 2vtr-x_r\ge 2vtl-x_l，问是否可拓展至 l=1,r=n。

这就是双序列拓展。将 x_{s\sim 1}（x_{1\sim s} 翻转） 和 x_{s\sim n} 做双序列拓展即可。

AC Code

#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 1e5 + 5 , inf = 1e18 + 7 , INF = inf * inf;
int x[N];
namespace Check
{
    int n , m;
    int a[N] , b[N] , prex1[N] , prey1[N] , nxtx1[N] , nxty1[N] , prex2[N] , prey2[N] , nxtx2[N] , nxty2[N];
    bool check1 (int px , int py)
    {
        if (px == 0 || py == 0) return 1;
        if (a[prex2[px]] < b[prey2[py]]) return check1 (prex2[px] - 1 , py);
        if (a[prex1[px]] < b[prey1[py]]) return check1 (px , prey1[py] - 1);
        return 0;
    }
    bool check2 (int px , int py)
    {
        if (px == n + 1 || py == m + 1) return 1;
        if (a[nxtx2[px]] < b[nxty2[py]]) return check2 (nxtx2[px] + 1 , py);
        if (a[nxtx1[px]] < b[nxty1[py]]) return check2 (px , nxty1[py] + 1);
        return 0;
    }
    bool check (int p , int siz , int t , int v)
    {
        a[0] = b[0] = -INF;
        n = p , m = siz - p + 1;
        a[n + 1] = b[m + 1] = INF;
        for (int i = p;i >= 1;i --) a[p - i + 1] = 2 * t * v * i - x[i];
        for (int i = p;i <= siz;i ++) b[i - p + 1] = 2 * t * v * i - x[i] + 1;
        prex2[0] = nxtx2[n + 1] = n + 1 , prey2[0] = nxty2[m + 1] = m + 1;
        for (int i = 1;i <= n;i ++)
        {
            prex1[i] = prex1[i - 1];
            if (a[prex1[i]] < a[i]) prex1[i] = i;
            prex2[i] = prex2[i - 1];
            if (a[prex2[i]] > a[i]) prex2[i] = i;
        }
        for (int i = n;i >= 1;i --)
        {
            nxtx1[i] = nxtx1[i + 1];
            if (a[nxtx1[i]] < a[i]) nxtx1[i] = i;
            nxtx2[i] = nxtx2[i + 1];
            if (a[nxtx2[i]] > a[i]) nxtx2[i] = i;
        }
        for (int i = 1;i <= m;i ++)
        {
            prey1[i] = prey1[i - 1];
            if (b[prey1[i]] < b[i]) prey1[i] = i;
            prey2[i] = prey2[i - 1];
            if (b[prey2[i]] > b[i]) prey2[i] = i;
        }
        for (int i = m;i >= 1;i --)
        {
            nxty1[i] = nxty1[i + 1];
            if (b[nxty1[i]] < b[i]) nxty1[i] = i;
            nxty2[i] = nxty2[i + 1];
            if (b[nxty2[i]] > b[i]) nxty2[i] = i;
        }
        if (a[prex2[n]] >= b[prey2[m]] || b[prey1[m]] <= a[prex1[n]]) return 0;
        return check1 (n , m) && check2 (1 , 1);
    }
}
int n , k , t;
void read (int &X)
{
    long long A;
    cin >> A;
    X = A;
}
signed main ()
{
    ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
    read (n) , read (k) , read (t);
    for (int i = 1;i <= n;i ++)
        read (x[i]);
    int l = 0 , r = 1e9 , mid;
    while (l < r)
    {
        mid = l + r >> 1;
        if (Check::check (k , n , t , mid)) r = mid;
        else l = mid + 1;
    }
    cout << (long long)r;
    return 0;
}