DFS能过！！！

这题非常简单， 要满足对于每个ai， 有 2 ≤ ∣ai - i∣ ≤ 3，只需要DFS时， 枚举每个ai为{i-3,i-2,i+2,i+3}即可。 最后， 如果没有一种可行的排列， 输出-1。

AC代码

#include <bits/stdc++.h>
using namespace std;

int n,f[100005];
bool flag = false,b[100005];

void dfs(int step){
    if(step>n){/可行
        for(int i = 1;i <= n;i++) cout << f[i] << ' ';
        cout << endl;
        flag = true;/有解
    }
    if(flag) return;/已经有解就不用继续了
    if(step-3>0&&!b[step-3]) {/枚举ai = i-3
    	b[step-3] = true;
    	f[step] = step-3;
    	dfs(step+1);
    	b[step-3] = false;
    }
    if(step-2>0&&!b[step-2]){/枚举ai = i-2
    	b[step-2] = true;
        f[step] = step-2;
        dfs(step+1);
        b[step-2] = false;
    }
    if(step+2<=n&&!b[step+2]){/枚举ai = i+2
    	b[step+2] = true;
        f[step] = step+2;
        dfs(step+1);
        b[step+2] = false;
    }
    if(step+3<=n&&!b[step+3]){/枚举ai = i+3
    	b[step+3] = true;
        f[step] = step+3;
        dfs(step+1);
        b[step+3] = false;
    }
}

int main(){
    cin >> n;
    dfs(1);
    if(!flag) cout << -1 << endl;/无解
    return 0;
}