题解 P5823 【【L&K R-03】课表的排列】

· · 题解

时间凑不上，比赛没能打成，发个题解来弥补一下……

第一眼看到样例，突然产生一种瞎猜的想法：是否只要先输出n以内的正整数，再输出当中的奇数，最后输出偶数就行了呢？

算了一下，发现这种乱搞解法在n=5和n=7时同样正确，于是尝试提交一下居然还真过了？

不管怎么凑巧，不管窝运气到底怎么爆棚，这种方法必须要经过证明才可以算得上正解。

于是便有了这篇题解。

证明过程：

啊啊啊一开始把\large\frac{1}{2}当成2了害得窝算了好久都不对qwq

咱们先设当前计算的为第k门科目，n为科目总数。

这时的k便出现了两种可能的情况：

1. 奇数

图纯手画真的很丑

显然两个k之间的差为

\frac{k+1}{2}+n-k

这里要注意坑点：间隔数比两数差少1，即此结果仍需减去1，即间隔数应为

\frac{k+1}{2}+n-k-1

化简后得

n-\frac{k+1}{2}

显然易发现，k越小，该式结果越大，且每相邻两个奇数代入该式后得到的结果相差1，换句话说，在k为奇数时，间隔数排序后恰好为一个公差为1的等差数列！

2. 偶数

接着上面的无敌丑图继续画，即可得到偶数的间隔：

\frac{k}{2}+n+\frac{n+1}{2}-k-1

化简后得

\frac{3n-k+1}{2}

显然结果与奇数一样，在k为偶数时，间隔数排序后也恰好为一个公差为1的等差数列！

既然奇偶数都为等差数列，咱们就可以看这两个等差数列是否能拼成一个等差数列了。

奇数的间隔数列最小到n-\large\frac{n+1}{2}=\frac{n-1}{2}，最大到n-1；偶数的间隔数列最小到\frac{3n\ -\ (n\ -\ 1\ +\ 1)}{2} =n，最大到\large\frac{3n-3}{2}，显然两者可拼接为一个公差为1的等差数列。

证明完毕。

有了这个证明，我们即可得出程序：

#include <bits/stdc++.h>
#define rp cout << i << " ";   //懒
using namespace std;
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)    rp  //输出全数列
    for (int i = 1; i <= n; i += 2) rp  //输出奇数
    for (int i = 2; i < n; i += 2)  rp  //输出偶数
    return 0;  //完结撒花～
}