[ARC120E] 1D Party 题解

PosVII · 2024-07-25 15:47:42 · 题解

前言

小清新 O(n) dp。

思路

首先考虑在出现第一次相遇之前，一定会有一对相邻的人走的方向相反，原因显然。

我们已知每次相遇后，整个序列就会一分为二，变为子问题。

样例三提示我们同时并非只有一对相邻的人方向相反，相遇是在同时进行的。

当序列长度 \le 3 时，最优策略一定是 \frac{(a_r - a_l)}{2}。否则某个序列长度 \ge 4 时，一定存在一种分割使得答案更优秀。

不存在被分割长度为 1 的序列，因为此时它一定在边上或者一定有一个分割是属于某个长度 \le 3 的序列的。

每个长度为 3 或 4 的分割的时间为 \frac{(a_{r+1}-a_{l-1})}{2}，使用 dp 求最小时间即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=2e5+5;
int n,a[MAXN],f[MAXN];
signed main() {
    #ifndef ONLINE_JUDGE
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    #endif
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    a[0]=a[1],a[n+1]=a[n];
    f[1]=1e9;
    for(int i=2;i<=n;++i) {
        f[i]=max(f[i-2],(a[i+1]-a[i-2])/2);
        if(i>=3) f[i]=min(f[i],max(f[i-3],(a[i+1]-a[i-3])/2));
    }
    printf("%d",f[n]);
    return 0;
}