Yuki 210 探し物はどこですか？ ( Expectation, Priority Queue )

No.210 探し物はどこですか？ - yukicoder

題意：
有若干個房間，我們想找到一個藏在某處的寶物，而每個房間有寶物的機率為 P / 1000，如果該房間確實有寶物，則每次檢查這個房間會找到寶物的機率為 Q / 100。求最佳檢查順序下，能找到寶物的最小期望檢查次數是多少。

資料規模：
1≤n≤1000
0≤pi≤1000
1≤qi≤100
∑ni=1,pi=1000
時限 2000 ms
記憶體 512 MB

解法：
首先有一種直覺，總是檢查當前找到寶物機率最高的房間一定是最優的。稍微想一下就知道是正確的，因為回合小的分配給機率大的，回合大的分配給機率小的，總和一定會是最小。因此，直到回合數和當前能找到寶物的最高機率的乘積小到可忽略為止取總，便是答案。

時間 / 空間複雜度：
O( N lg N + ( try = 1e6 ) * lg N ) / O( N )

int N;
vi P;
vi Q;

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

double ans;

void preprocess(){
  priority_queue< tuple< double, int > > pq;
  for( int i = 0; i < N; ++i )
    pq.emplace( P[ i ] / 1000. * Q[ i ] / 100., i );
  for( int i = 1; i <= 1000000; ++i ){
    double p; int id; tie( p, id ) = pq.top(); pq.pop();
    ans += p * i;
    pq.emplace( p * ( 1.0 - Q[ id ] / 100. ), id );
  }
}

void solve(){
  cout << fixed << setprecision( 5 ) << ans << endl;
}