很好的一道思维题。
容易发现答案下界是 \(0\),手模几组发现好像都能取到,考虑能不能找到构造答案为 \(0\) 的通解。
那么除了 \(i=n\) 以外的所有 \(i\) 都应该有 \(d_i=n-i\),考虑构造这个东西,然后最后 \(n\) 随便放在剩余的空位上。
你把 \(2n\) 个位置分成前后两个 \(n\),前 \(n\) 个往内收缩插 \(i\) 为奇数的,后 \(n\) 个往内收缩插 \(i\) 为偶数的。容易发现这样构造是对的。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int n,a[N<<1];
signed main(){cin>>n;int l1=1,r1=n,l2=n+1,r2=(n<<1)-1;for(int i=1;i<n;i++){if(i&1)a[l1]=a[r1]=i,l1++,r1--;else a[l2]=a[r2]=i,l2++,r2--;}for(int i=1;i<=(n<<1);i++)cout<<(a[i]?a[i]:n)<<" ";return 0;
}