数列 $(a_i)_{i=0}^{n-1}$ が与えられたとき、$a_i/j\ (i=0,\ldots, n-1,\ j=1,2.\ldots)$ の top K を求める
| $a_0$ | $a_1$ | $a_2$ | |
|---|---|---|---|
| ÷1 | $a_0$ | $a_1$ | $a_2$ |
| ÷2 | $a_0/2$ | $a_1/2$ | $a_2/2$ |
| ÷3 | $a_0/3$ | $a_1/3$ | $a_2/3$ |
例えば Priority Queue を使うと求められる。最初に $a_0,\ldots, a_{n-1}$ を Priority Queue に入れて、大きい方から取り出していく。$a_i$ を取り出したら、$a_i/2$ を入れるというのを繰り返す。
問題: 数列 $(a_i){i=0}^{n-1}$ と数列 $(b_j){j=0}^{m-1}$ が与えられたとき、 $a_i+b_j\ (i=0,\ldots, n-1,\ j=1,\ldots,m-1)$ の top K を求める
| $a_0$ | $a_1$ | $a_2$ | $a_3$ | |
|---|---|---|---|---|
| $b_0$ | $a_0+b_0$ | $a_1+b_0$ | $a_2+b_0$ | $a_3+b_0$ |
| $b_1$ | $a_0+b_1$ | $a_1+b_1$ | $a_2+b_1$ | $a_3+b_1$ |
| $b_2$ | $a_0+b_2$ | $a_1+b_2$ | $a_2+b_2$ | $a_3+b_2$ |
$(b_j)_{j=0}^{m-1}$ をソートすれば、ドント式と同様に Priority Queue で求められる。