CFR 732 D. Exams ( Binary Search + Greedy )

Problem - D - Codeforces
二分搜答案，對於所有考試，一定考最後一個日期，這時候就變區間置點問題，所有考試對應一個區間，且在該區間必須放置 k 個點。
注意考試時不能讀書。

bool cmp( pii a, pii b ){
    if( a.first != b.first )
        return a.first > b.first;
    return a.second < b.second;
}

bool ok( vi d, vi a, int x ){
    set< int > vis;
    set< int > td;
    priority_queue< pii, vp, greater< pii > > pq;
    for( int i = x - 1; i >= 0; --i ){
        if( d[ i ] == 0 or vis.count( d[ i ] ) )
            continue;
        vis.insert( d[ i ] );
        td.insert( i );
        pq.push( pii( i, a[ d[ i ] - 1 ] ) );
        // cout << i << " " << a[ d[ i ] - 1 ] << endl;
    }
    if( vis.size() != a.size() )
        return false;
    for( int i = 0; i < x; ++i ){
        if( td.count( i ) )
            continue;
        if( pq.empty() )
            return true;
        int r = pq.top().first;
        int q = pq.top().second;
        pq.pop();
        // cout << i << r << q << endl;
        if( i >= r )
            return false;
        if( q - 1 > 0 )
            pq.push( pii( r, q - 1 ) );
    }
    return pq.empty();
}

void solve(){
    int N, M; cin >> N >> M;
    vi D( N );
    for( int i = 0; i < N; ++i )
        cin >> D[ i ];
    vi A( M );
    for( int i = 0; i < M; ++i )
        cin >> A[ i ];
    // cout << ok( D, A, 9 ) << endl; return;
    int lb = 1, rb = N;
    int ans = -1;
    while( lb <= rb ){
        int mid = lb + rb >> 1;
        if( ok( D, A, mid ) )
            ans = mid, rb = mid - 1;
        else
            lb = mid + 1;
    }
    cout << ans << endl;
}