在一群 M 個數字中,如果有某個數字出現的次數超過 M/2,則稱為此數為這群數的「絕對多數」,
一群數字最多有一個絕對多數,但也可能沒有,例如(1,2,1,1,3)的絕對多數是 1,
而(1,2,1,3)沒有絕對多數,本題的任務是計算絕對多數。
每一筆測試資料包含一個 N×N 的整數方陣 A 與 q 個計算要求,矩陣的元素儲存在A[0][0]~A[N-1][N-1],
矩陣的橫的一排稱為列(row),直的一排稱為行(column)。
每一個計算要求包含四個整數 r1、r2、c1、c2,0 <= r1 <= r2 < N,0 <= c1 <= c2 < N,
代表一個子矩陣 A[r1:r2][c1:c2],也就是第 r1列到第 r2列且第 c1行到第 c2行所組成的子矩陣,
我們要計算這個子矩陣中是否有絕對多數。
下圖為一個 N=5 的方陣 A,子矩陣 A[0:1][0:2]共有六個元素,出現最多的元素是 1,出現了 3 次,並未超過總數的一半,因此沒有絕對多數。
而子矩陣 A[2:4][1:3]共有 9 個元素,3 出現了 5 次,超過總數的一半,因此絕對多數是 3。
對於某些子題,你的程式必須很有效率的決定是否存在絕對多數。
輸入包含多個測試資料,每筆測試資料包含一個輸入矩陣以及若干個子矩陣計算要求。
每個測試資料的第一行(line)是矩陣大小的 N,接下來 N 行(lines)是矩陣內容,以row-major 方式排列,
由第 0 列(row)至第 N-1 列,每列有 N 個非負整數是該列第 0 行(column)至第 N-1 行(column),數字之間以一個空白間格。
接著一行包含一個整數 q 代表計算要求數,其下有 q 行,每行是一個計算要求依序是子矩陣範圍的四個整數r1,r2,c1,c2。
一筆測試資料結束後是下一筆測試資料,若 N=0 代表輸入資料結束。
針對每個測試資料的每個計算要求,以一行輸出絕對多數,如果沒有絕對多數則輸出-1。
5 1 2 3 3 2 2 1 1 2 3 1 2 3 1 1 0 2 3 3 1 0 3 1 3 2 2 0 1 0 2 2 4 1 3 0
-1 3
公開 測資點#0 (33%): 3.0s , <1M
公開 測資點#1 (33%): 3.0s , <50M
公開 測資點#2 (34%): 3.0s , <50M
本題共有四組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
每組測試資料的輸入檔參數 N、D、Q 和 S 如下,其中 N 是矩陣大小的上限,D 代表陣列中數字
的上限,Q 是計算需求總數即該檔案中 q 值的總和,也就是該子題總共輸出 Q 行,S 則
是輸入檔案中,所有矩陣的元素總量,即 N2的總和。
第一組 15 分, N <= 100 、D <= 5000 、Q <= 40、S <= 32000。
第二組 27 分, N <= 1010、D <= 5000 、Q <= 30、S <= 3200000。
第三組 19 分, N <= 1010、D <= 2^31-1、Q <= 50、S <= 3200000。
第四組 39 分, N <= 2000、D <= 2^31-1、Q <= 70、S <= 12500000。
測資看起來是 rand() !
第四筆因為檔案太大無法上傳～～
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||