CF359B Permutation 题解
分析
小清新构造题。
不难发现,对于一个有序序列,假设是 \[ [1,2,3,4,5,6] \] 那么 \[ \sum_{i=1}^3 | a_{2i} - a_{2i-1} | = | \sum_{i=1}^3 a_{2i} - a_{2i-1} | = 3 \] 把 \(2\) 提前, \[ [2,1,3,4,5,6] \] 发现得到的结果是 \(2\)。
把 \(3\) 提前, \[ [3,1,2,4,5,6] \] 发现得到的结果是 \(4\)。
把 \(j\) 提前,\(a_2-a_1=1 - j = -(j-1)\),而在左式中直接绝对值没了,对答案贡献 \(j-1\),而右式则会让答案减少 \(j-1\)。其他的都是一一对应的,一减就没了。那么把 \(j\) 提前的答案就是 \(2 \cdot (j-1)\)。
直接把 \(k+1\) 提前,其他的顺序输出。
CODE
#include<bits/stdc++.h>
using namespace std;
int n, k;
int main() {
scanf("%d%d",&n,&k), n<<=1;
printf("%d ",k+1);
for(int i=1;i<=k;++i) printf("%d ",i);
for(int i=k+2;i<=n;++i) printf("%d%c",i," \n"[i==n]);
}
CF359B Permutation 题解
https://yozora0908.github.io/2022/cf359b-solution/