{%hackmd @ioncamp/__style %}
# [CSES 2215](https://cses.fi/problemset/task/2215/)

## 題目

- 構造一個 $1..n$ 的排列使得他的 **最長單調子序列** 恰好長度為 $k$

- **最長單調子序列** 是指這個子序列單調遞增或單調遞減

## 想法

> $\texttt{LIS}$ 為 $\texttt{longest increasing subsequnce}$
>
> $\texttt{LDS}$ 為 $\texttt{longest decreasing subsequnce}$

### 觀察

- $\texttt {ans} = \texttt{max} \begin{cases} \texttt{len(LIS)} \\ \texttt{len(LDS)}\end{cases}$

- 發現說要想使答案控制得很好需要使得 $\texttt{len(LIS)}$ 跟 $\texttt{len(LDS)}$ 取得平衡

- 例如 $n=9,k=3$ 那我必須使得 $\texttt{len(LIS) = len(LDS) = 3}$

- 使得 $\texttt{LIS}$ 和 $\texttt{LDS}$ 不互相影響

- $[\underline{\color{red}3 \color{black},2,1},\underline{\color{red}6 \color{black},5,4},\underline{\color{red}9 \color{black},8,7}]$

- 紅色為其中一個 $\texttt{LIS}$ 底線為 $\texttt{LDS}$

### 證明

> $\texttt{proof:}$
>
> $k < \sqrt{n}$ 無解

- 假設存在一個長度 $n=k^2+1$ 的排列 $p$，它的 $\texttt{LIS}$ 與 $\texttt{LDS}$ 長度皆最多為 $k$
- 此時 $k<\sqrt{n}$
- $a_i=$ 以 $a_i$ 結尾的 $\texttt{LIS}$ 長度
- $b_i=$ 以 $b_i$ 結尾的 $\texttt{LDS}$ 長度
- 對於所有 $i$ ， $1 \le a_i,b_i\le k$ (我們的假設)
- 因為 $(a_i,b_i)$ 有 $k^2$ 種可能 (籠子)
- 但目前 $i=1..k^2+1$ 有 $k^2+1$ 種 (鴿子)
- 可由鴿籠原理得知必存在兩數 $i,j$ 使 $a_i=a_j,b_i=b_j,(i<j)$

> 鴿籠原理
>
> - 若有 $n$ 個籠子和 $n+1$ 隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少 $2$ 隻鴿子。

- 那接著分以下 $\texttt{case:}$
- $\texttt{case1:}$ $p_i<p_j$
- 此時 $a_i=a_j$ 矛盾 (以 $p_i$ 結尾的 $\texttt{LIS}$勢必可以再接上 $p_j$，使 $a_j=a_i+1$ )
- $\texttt{case2:}$ $p_i>p_j$
- 此時 $b_i=b_j$ 矛盾 (以 $p_i$ 結尾的 $\texttt{LDS}$ 勢必可以再接上 $p_j$，使 $b_j=b_i+1$ )

- 故假設錯誤，代表 $\texttt{len(LIS),len(LDS)}$ 長度會比 $k$ 大，代表 $k<\sqrt{n}$ 無解

### 構造

- 構造方法如上面 $n=9,k=3$ 的那個方法一樣
- 分成 $n/k$ 段，每一段從大排到小，兩段之間的開頭必須是從左到右遞增
- 如果不夠讓每一段長度都是 $k$ ，那最後一段不用填滿沒關西
- 例如 $n=8,k=3$
- $[3,2,1,6,5,4,8,7]$

## CODE

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pb push_back
#define mk make_pair
#define F first
#define S second
#define ALL(x) x.begin(), x.end()

using namespace std;
using PQ = priority_queue<int, vector<int>, greater<int>>;
 
const int INF = 2e18;
const int maxn = 3e5 + 5;
const int M = 1e9 + 7;

int n, m, k;

// 向下取整
int ifloor(int a, int b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}
 
// 向上取整
int iceil(int a, int b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

void init() {
    cin >> n >> k;
}

// 開根號
int sqt (int x) {
    int tmp = sqrt (x);
    if (tmp * tmp < x) tmp++;

    return tmp;
}

void solve() {
    m = sqt (n);
    if (k < m) {
        cout << "IMPOSSIBLE\n";
        return;
    }

    int num = iceil(n, k); // 分幾段
    // 每一段有 k 個東西, 共 n/k 段
    int pre = 0, start = k;
    for (int i = 0; i < num; i++) {
        // 3 2 1 6 5 4 9 8 7
        for (int j = start; j > pre; j--) {
            cout << j << " ";
        }
        pre = start;
        start += k;
        if (start > n) start = n; // 太大變 n
    }
    cout << "\n";
} 
 
signed main() {
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        init();
        solve();
    }
} 

## 參考資料
- https://abc864197532.github.io/2021/09/15/cses-additional-sol/

###### tags: `題解`