CFR 589 G. Hiring ( Segment Tree, Binary Search )

Problem - G - Codeforces

題意：
給 M 個工作時間，N 個人的特徵 D[ i ] 與 R[ i ]，代表第 i 個人在一天工作時，需要前 D[ i ] 單位時間預熱，然後才能開始算入工作時數，而每一天的工作時數總和起來需要 R[ i ]。問分別每個人會在第幾天做完他的作業，做不完輸出 0。

資料規模：
N, M ≤ 2e5
T, R ≤ 1e6
TL: 4000 ms
ML: 512 MB

解法：
將每個人按 D 值由大到小排序後，考慮一顆線段樹，這棵樹上只有 T 值比當前考慮這個 D 值大的，那麼只要維護區間裡有多少個元素，和 T 的總和是多少，就能判斷夠不夠抵銷還需要做的時數 ( 總和 - 元素數量 * D = 貢獻 )。也就是可以在線段樹上直接進行二分搜，如果左子樹夠，就往左子樹走，不夠就扣掉左子樹的貢獻，往右子樹走。

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

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

typedef long long ll;

const int MAXN = ( int ) 2e5;
const int MAXM = ( int ) 2e5;

int N, M;
int T[ MAXM ];
int D[ MAXN ], R[ MAXN ];
int ord_d[ MAXN ]; // sort by D large to small
int ord_t[ MAXM ]; // sort by R large to small
int ans[ MAXN ];

struct Segment_Tree{
  ll sum[ MAXM << 3 ];
  int cnt[ MAXM << 3 ];
  void modify( int t, int lb, int rb, int k, int v ){
    if( lb + 1 == rb ){
      sum[ t ] = v;
      cnt[ t ] = 1;
      return;
    }
    int mid = lb + rb >> 1;
    if( k < mid ) modify( t << 1, lb, mid, k, v );
    else modify( t << 1 | 1, mid, rb, k, v );
    sum[ t ] = sum[ t << 1 ] + sum[ t << 1 | 1 ];
    cnt[ t ] = cnt[ t << 1 ] + cnt[ t << 1 | 1 ];
  }
  void dfs( int t, int lb, int rb, int s, int d, int &ans ){
    if( lb + 1 == rb ){
      if( s <= 0 ) return ( void ) ( ans = lb );
      s -= sum[ t ] - cnt[ t ] * d;
      if( s <= 0 ) return ( void ) ( ans = rb );
      assert( rb == M );
      return ( void ) ( ans = 0 );
    }
    int mid = lb + rb >> 1;
    ll lft = sum[ t << 1 ] - 1LL * d * cnt[ t << 1 ];
    if( s <= lft ) return dfs( t << 1, lb, mid, s, d, ans );
    return dfs( t << 1 | 1, mid, rb, s - lft, d, ans );
  }
} segt;

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < M; ++i ){
    cin >> T[ i ];
    ord_t[ i ] = i;
  }
  for( int i = 0; i < N; ++i ){
    cin >> D[ i ] >> R[ i ];
    ord_d[ i ] = i;
  }
  sort( ord_t, ord_t + M, [ & ]( int i, int j ){ return T[ i ] > T[ j ]; } );
  sort( ord_d, ord_d + N, [ & ]( int i, int j ){ return D[ i ] > D[ j ]; } );
  {
    int ptr_ord_t = 0;
    for( int i = 0; i < N; ++i ){
      while( ptr_ord_t < M and T[ ord_t[ ptr_ord_t ] ] >= D[ ord_d[ i ] ] ){
        segt.modify( 1, 0, M, ord_t[ ptr_ord_t ], T[ ord_t[ ptr_ord_t ] ] );
        ++ptr_ord_t;
      }
      segt.dfs( 1, 0, M, R[ ord_d[ i ] ], D[ ord_d[ i ] ], ans[ ord_d[ i ] ] );
    }
  }
  for( int i = 0; i < N; ++i ){
    cout << ans[ i ] << " \n"[ i + 1 == N ];
  }
  return 0;
}