P12675

DDF_ · 2025-09-25 20:08:15 · 题解

题解

诡异的贪心。

有四种策略：

1. 将头尾并成一样的，直接全赋值为 -10^{9}；
2. 处理开头一段和结尾一段，使得这两段直接并在一起。
3. 处理开头一段和结尾一段，将端点后的元素加成相同的，赋值中间一段。
4. 处理开头一段和结尾一段，此时开头结尾这两段全为 -10^{9}，取这两段的最靠近端点赋值中间一段。

对于一个点 i，可以处理它与 a_{1} 的差值 s_{i} 和与 a_{n} 的差值 c_{i}。

先预处理 ans 为第一策略的答案。

处理前缀 s_{i} 最小值 M_{i}，容易发现由于这个数组是 1\sim n 的排列，因此会有两个位置满足 s_{x}=s_{y}=M_{i} 的情况，可以开两个变量存储这两个位置。当枚举到 i 作为右端点时，依次考虑这两个位置的最小贡献（第三、第四策略，注意左右端靠在一起和左右端中间只有一个位置的情况不能使用），并且特判左端点右端点靠在一起的情况即可（第二策略）。

:::info[补：贪心证明] 可以发现答案至少为 n，考虑最小化多出来的答案。

处理完前后两端后，此时用上文第二个策略可以使得多余贡献至多为 2，对于中间任意一个位置，考虑使端点前后的位置与它相等，至少加 2 次，不会更优。

考虑让端点前后的点相等，可以只加一次，可能会更优。对于端点靠在一起的情况不需要多余操作，也会更优。 :::

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
const ll inf=1e15;
int _;
int n;
ll a[N],c1[N],c2[N],ans;
ll mnc,pl1,pl2;
void solve() {
    memset(c1,0,sizeof c1),memset(c2,0,sizeof c2);
    scanf("%d",&n),mnc=inf,pl1=pl2=0;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    ans=abs(a[n]-a[1]);
    for(int i=2;i<n;i++) {
        c1[i]=abs(a[i]-a[1]),c2[i]=abs(a[n]-a[i]);
        if(i>2) ans=min(ans,c2[i]+c1[i-1]);
        if(pl1!=i-1&&pl1!=i-2) ans=min(ans,c2[i]+mnc+min(2ll,abs(a[pl1+1]-a[i-1])));
        if(pl2!=i-1&&pl2!=i-2) ans=min(ans,c2[i]+mnc+min(2ll,abs(a[pl2+1]-a[i-1])));
        if(c1[i]<mnc) pl1=i,pl2=0,mnc=c1[i];
        if(c1[i]==mnc) pl2=i;
    }
    printf("%lld\n",ans+n);
    return;
}
int main() {
    scanf("%d",&_);
    while(_--) solve();
    return 0;
}