740-C. Alyona and mex

2021-03-17 23:50:32 +0800 CST Tags: sequence

出處：https://codeforces.com/contest/740/problem/C
提交：https://codeforces.com/contest/740/submission/110167700

問題：給定所求陣列之長度 $n\in[1,10^5]$ 以及 $m\in[1,10^5]$ 組描述該陣列之子區間的索引值。現在限定這個陣列只能承裝非負整數，而先前給定的 m 組子區間都各自會有一個不屬於該區間元素的最小非負整數，舉例來說，[0,5,3,1] 所對應到的「最小不包含非負整數」是為 2。如果我們希望現在找到的陣列、它的指定子區間們所對應到的「最小不包含非負整數」們要最大，請問這個值是多少？此時的全域陣列內容為何？

解法：很明顯地，這個最大值必須剛好是所有的給定子區間裡面最短的長度。舉例來說，長度為 4 的子區間我們塞 [0,1,2,3] 會對應到「最小不包含非負整數」4，但是如果塞其他元素的話這個值勢必會往下掉，可以想成有空隙露出來的概念。至於其他的子區間因為長度不會更短，所以更有空間可以填滿 0、1、2、3 這四個數字。現在問題來了！當兩個子區間有重疊的時候，要怎麼保證它們的元素都滿足這個條件而不互相衝突？參考解法提供的元素填法非常酷炫！它主張當答案為 len 的時候，只要按照 0,1,2,…,len-1,0,1,2,…,len-1,… 的要領下去填充，就能保證每個長度不小於 len 的子區間都至少包含 0 到 len-1 的所有元素！

實作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <bits/stdc++.h>
using namespace std;

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    int n, m, a, b, len;
    cin >> n >> m; len = INT_MAX;
    for (int i=0; i<m; i++) {
        cin >> a >> b;
        len = min(len, b-a+1);
    }
    cout << len << '\n'; m = 0;
    for (int i=0; i<n; i++) {
        cout << m << " ";
        m = (m+1) % len;
    }
    return 0;
}

結果：