首先观察样例，不难发现有可能\(k\)为奇的时候无解
证明：《离散数学》中有一道题目的trick是\(|i-j|\)与\(i+j\)的奇偶性相同，所以曼哈顿排列的奇偶性与\(p_1+1+p_2+2+...+p_n+n=2(1+2+3+...+n)\)，后者显然为偶数，所以\(k\)为奇时无解
其次一个很自然的想法就是当\(p\)为\([n,n-1,n-2,...,3,2,1]\)时，曼哈顿排列最大，所以当\(k\)超过最大值的时候无解
证明：用反证法证明。如果存在\(p_i<p_j,i<j\)，那么交换\(p_i\)和\(p_j\)之后分类讨论可知答案不会更差
其余情况可以知道\(k\)都有解，下面考虑构造
一个比较自然的想法就是先快速接近\(k\)，依靠曼哈顿排列最大的时候，此时贡献分别为\(2(n-1),2(n-3),...\)，每次计算贡献的时候都将\(k\)减掉对应的贡献，某一时刻\(k\)小于当前时刻的贡献的时候，由于\(k\)为偶数，所以将\(k/2\)，然后对当前数\(i\)找到\(i+\frac{k}{2}\)即可，剩下的数都不错排
看不懂见代码，比较easy
标签：...,曼哈顿,Permutations,奇偶性,贡献,Manhattan From： https://www.cnblogs.com/dingxingdi/p/18341835