CFR 439 D. Devu and his Brother ( Ternary Search )

Problem - D - Codeforces

題意：
給兩個陣列，每次操作可以選一個陣列中的一個數字對其加一或減一。求至少要多少次操作，才能使得第一個陣列中最小的數字不小於第二個陣列中最大的數字。

資料規模：
數列大小： 1 ≤ N, M ≤ 1e5
數字大小： 1 ≤ A[ i ], B[ i ] ≤ 1e9
時間限制：1000 ms
空間限制：256 MB

解法：
對關鍵值三分搜，因為想一下就能發現離最好的關鍵值遠，代價一定不會變好。

時間 / 空間複雜度：
O( log( max{ A } ) * ( N + M ) ) / O( N + M )

int N, M;
vi A;
vi B;

void init(){
  cin >> N >> M;
  A = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
  B = vi( M );
  for( int i = 0; i < M; ++i ){
    cin >> B[ i ];
  }
}

ll get_cost( int apex ){
  ll res = 0;
  for( int i = 0; i < N; ++i ){
    if( A[ i ] < apex ){
      res += apex - A[ i ];
    }
  }
  for( int i = 0; i < M; ++i ){
    if( B[ i ] > apex ){
      res += B[ i ] - apex;
    }
  }
  return res;
}

void preprocess(){
  int lb, rb;
  for( lb = 1, rb = ( ll ) 1e10; rb - lb > 10; ){
    int x = ( 2LL * lb + rb ) / 3;
    int y = ( 2LL * rb + lb ) / 3;
    ll cl = get_cost( lb );
    ll cx = get_cost( x );
    ll cy = get_cost( y );
    ll cr = get_cost( rb );
    if( cl <= cx and cx <= cy and cy <= cr ){
      rb = x;
    } else if( cl >= cx and cx <= cy and cy <= cr ){
      rb = y;
    } else if( cl >= cx and cx >= cy and cy <= cr ){
      lb = x;
    } else if( cl >= cx and cx >= cy and cy >= cr ){
      lb = y;
    } else{
      assert( false );
    }
  }
  ll ans = 1LL << 62;
  for( int i = lb; i <= rb; ++i ){
    upmin( ans, get_cost( i ) );
  }
  cout << ans << endl;
}