CFR 767 D. Cartons of milk ( Binary Search, Counting Sort )

Problem - D - Codeforces

題意：
你有 N 個牛奶，第 i 瓶會在 A[ i ] 天後壞掉。商店有 M 個牛奶，第 i 瓶會在 B[ i ] 天後壞掉。你一天喝至多 K 瓶牛奶，問最多可以買多少牛奶，使得你不必喝任何壞掉的牛奶。

資料規模：
N, M ≤ 1e6
過期天數 ≤ 1e7
TL: 2000 ms
ML: 256 MB

解法：
對答案二分搜，注意要用 counting sort，不然會超時。

時間 / 空間複雜度：
O( 過期天數 * lg M ) / O( 過期天數 )

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

const int MAXN = ( int ) 1e6;
const int MAXM = ( int ) 1e6;

int N, M, K;
int refg[ MAXN ];
int shop[ MAXM ];
int sord[ MAXM ];

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N >> M >> K;
    for( int i = 0; i < N; ++i ){
      cin >> refg[ i ];
    }
    for( int i = 0; i < M; ++i ){
      cin >> shop[ i ];
      sord[ i ] = i;
    }
    sort( sord, sord + M, [ & ]( int i, int j ){ return shop[ i ] > shop[ j ]; } );
  }
  {
    int ans = -1;
    for( int lb = 0, rb = M; lb <= rb; ){
      int mid = lb + rb >> 1;
      static int milk[ ( int ) 1e7 + 1 ];
      for( int i = 0; i < N; ++i ){
        ++milk[ refg[ i ] ];
      }
      for( int i = 0; i < mid; ++i ){
        ++milk[ shop[ sord[ i ] ] ];
      }
      int ng = 0;
      vector< int > gat;
      for( int i = 0; i <= ( int ) 1e7; ++i ){
        for( int j = 0; j < milk[ i ]; ++j ){
          gat.emplace_back( i );
        }
      }
      for( int i = 0; i < N + mid; i += K ){
        ng |= gat[ i ] < i / K;
      }
      if( not ng ){
        ans = mid;
        lb = mid + 1;
      } else{
        rb = mid - 1;
      }
      for( int i = 0; i < N; ++i ){
        --milk[ refg[ i ] ];
      }
      for( int i = 0; i < mid; ++i ){
        --milk[ shop[ sord[ i ] ] ];
      }
    }
    cout << ans << endl;
    if( ans != -1 ){
      for( int i = 0; i < ans; ++i ){
        cout << sord[ i ] + 1 << " \n"[ i + 1 == ans ];
      }
    }
  }
  return 0;
}