CFR 740 C. Alyona and mex ( Ad hoc )

Problem - C - Codeforces

題意：
給一堆區間，求一個陣列，使得所有區間的最小 mex 最大。

資料規模：
所求陣列長度 n, 區間數 m, 1 ≤ n, m ≤ 1e5
時限 2000 ms
記憶體 256 MB

解法：
考慮最短區間，長度就是最大最小 mex。因為只要由左而右，小到大填數字，並將右邊也都這麼做，左邊也都這麼做，任一個該長度的區間必然會滿足該 mex，更長的區間也一樣。而那同時是上限，所以必定是最佳解。

時間 / 空間複雜度：
O( N )

int N, M;
vp S;

void init(){
    cin >> N >> M;
    S = vp( M );
    for( int i = 0; i < M; ++i )
        cin >> S[ i ].first >> S[ i ].second, --S[ i ].first;
}

int len;
vi ans;

void preprocess(){
    nth_element( S.begin(), S.begin(), S.end(), [ & ]( pii a, pii b ){ return a.second - a.first < b.second - b.first; } );
    ans = vi( N );
    for( int i = S[ 0 ].first; i < S[ 0 ].second; ++i )
        ans[ i ] = i - S[ 0 ].first;
    len = S[ 0 ].second - S[ 0 ].first;
    for( int i = S[ 0 ].second, v = 0; i < N; ++i, v = ( v + 1 ) % len )
        ans[ i ] = v;
    for( int i = S[ 0 ].first - 1, v = len - 1; i >= 0; --i, v = ( v - 1 + len ) % len )
        ans[ i ] = v;
}

void solve(){
    cout << len << endl;
    for( int i = 0; i < N; ++i )
        cout << ans[ i ] << " \n"[ i + 1 == N ];
}