CFR 738 E. Subordinates ( Ad hoc )

Problem - E - Codeforces

題意：
給首領的編號，以及公司裡所有人各自的上級數量( 所有上級 )。求至少有多少人是謊報的。

資料規模：
1 ≤ n ≤ 2e5, 1 ≤ s ≤ n
0 ≤ ai ≤ n - 1
時限 1000 ms
記憶體 256 MB

解法：
首先檢查首領對不對，不對就直接改他。
接著看有沒有人是 0，有的話他一定要改。
考慮還有什麼情形是不合法的。如果存在一個上級數量 x，卻不存在一個上級數量 x - 1，那麼就是不合法的，反之合法。
將所有人的上級數量排序，由小至大考慮為可能會產生最佳解的序列的最大上級數量，所以比它大的所有上級數量都需要改。對於空的上級數量，優先用多餘 0 去補，如果已經沒有多餘 0，就將當前序列最大值改為它，繼續程序。

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

int acnt, bcnt; // extra for use / wrong

int maxa;
vi freq;

void preprocess(){
    if( A[ S - 1 ] != 0 )
        A[ S - 1 ] = 0, ++bcnt;
    sort( A.begin(), A.end() );
    int zcnt = 0;
    for( int i = 0; i < N; ++i ){
        if( A[ i ] == 0 )
            ++zcnt;
        else
            break;
    }
    if( zcnt > 1 )
        acnt += zcnt - 1, bcnt += zcnt - 1;
    maxa = A.back();
    freq = vi( maxa + 1 );
    for( int i = 0; i < N; ++i )
        ++freq[ A[ i ] ];
}

int ans;

void solve(){
    ans = N;
    for( int i = 0; i <= maxa; ++i ){
        if( freq[ i ] == 0 ){
            if( acnt )
                --acnt;
            else
                --freq[ A.back() ], A.pop_back(), ++bcnt;
        }
        upmin( ans, bcnt + A.size() - ( upper_bound( A.begin(), A.end(), i ) - A.begin() ) );
    }
    cout << ans << endl;
}