CSES 2215

題目

• 構造一個

  $1..n$ 的排列使得他的 最長單調子序列 恰好長度為
  $k$

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

想法

$\mathtt{\text{LIS}}$ 為

$\mathtt{\text{longest increasing subsequnce}}$

$\mathtt{\text{LDS}}$ 為

$\mathtt{\text{longest decreasing subsequnce}}$

觀察

• $\mathtt{\text{ans}}=\mathtt{\text{max}}\{\begin{array}{l}\mathtt{\text{len(LIS)}}\\ \mathtt{\text{len(LDS)}}\end{array}$

• 發現說要想使答案控制得很好需要使得

  $\mathtt{\text{len(LIS)}}$ 跟
  $\mathtt{\text{len(LDS)}}$ 取得平衡

• 例如

  $n=9,k=3$ 那我必須使得
  $\mathtt{\text{len(LIS) = len(LDS) = 3}}$

  • 使得

    $\mathtt{\text{LIS}}$ 和
    $\mathtt{\text{LDS}}$ 不互相影響

  • $[\underset{―}{3,2,1},\underset{―}{6,5,4},\underset{―}{9,8,7}]$

  • 紅色為其中一個

    $\mathtt{\text{LIS}}$ 底線為
    $\mathtt{\text{LDS}}$

證明

$\mathtt{\text{proof:}}$

$k<\sqrt{n}$ 無解

• 假設存在一個長度
  $n=k^2+1$ 的排列
  $p$，它的
  $\mathtt{\text{LIS}}$ 與
  $\mathtt{\text{LDS}}$ 長度皆最多為
  $k$
  • 此時
    $k<\sqrt{n}$
• $a_i=$ 以
  $a_i$ 結尾的
  $\mathtt{\text{LIS}}$ 長度
• $b_i=$ 以
  $b_i$ 結尾的
  $\mathtt{\text{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$ 隻鴿子。

• 那接著分以下

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

• 故假設錯誤，代表

  $\mathtt{\text{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: 題解