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/
作者
yozora0908
发布于
2022年7月3日
许可协议