給你一個 $n\times m$ 的矩陣 $A$，其中矩陣內的元素是由 $1\sim nm$ 之間的整數組成，且每個數字恰好出現一次（換句話說，該矩陣內的元素會是 $1\sim nm$ 之間的整數的一個排列 ）。此外，再給你兩個奇正整數 $h,w$，求對於所有大小為 $h\times w$ 的子矩陣的中位數的最小值為何？
精確來說也就是求 $\underset{1\le i\le i+h\le n, 1\le j\le j+w\le m}{\min}\{median(A[i:i+h][j:j+w])\}$。
第一行有四個正整數 $n,m,h,w$。
接下來 $n$ 行每行 $m$ 個正整數描述矩陣 $A$。
$1\le h\le n\le 3000$
$1\le w\le m\le 3000$
$h,w$ 都是奇數
$1\le A[i][j]\le nm$
所有 $1\sim nm$ 之間的正整數皆會在 $A$ 中出現恰好一次
輸出一個正整數代表題目所求。
5 5 3 3 23 20 18 1 25 10 14 11 7 9 16 5 8 13 15 3 17 4 6 22 12 24 19 2 21
8
由於 ddj 的環境較舊會把 vector 編譯出來的執行空間消耗多不少，建議使用靜態陣列解這題以免得到 MLE。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||