CF622D 题解

很好的一道思维题。

容易发现答案下界是 \(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;
}