b399. 優勢產品 - 高中生程式解題系統

內容

一份產品有很多屬性，把每一個屬性當作一個維度，當成 $D$ 個維度的向量，當維度越多時絕對支配 (各方面都是最好的) 的機率就越低。若把 $D = 2$，就是在二維空間中的支配點 (Zerojudge d555 平面上的極大點)。由於絕對優勢的產品隨著維度增加而變少，定義出一種相對優勢產品，給定一個 $K$，若 $p_i$支配 (k-dominate) $p_j$，必須滿足下列三條：

$\exists S' \subseteq S, \; |S'| = K$
$\forall s_r \in S', p_{i}.s_{r} \ge p_{j}.s_{r}$
$\exists s_t \in S', p_{i}.s_{t} > p_{j}.s_{t}$

用中文解釋這幾條數學公式，假設有 6 個維度的產品，目標 $K = 5$，則表示要在 6 的維度中任意挑選 5 個維度比較，若存在一種挑法可以支配，則可以說 $p_i$ k-dominate $p_j$

例如現在有 8 台筆記型電腦，共有 6 種屬性可以比較，數值越大越好。

Notebook	CPU	RAM	HDD	HDD S.	Q.	VRAM
N1	3	3	5	6	6	8
N2	9	4	9	7	7	9
N3	8	4	7	9	2	7
N4	5	6	8	9	5	9
N5	9	7	9	6	2	4
N6	6	6	6	5	3	5
N7	5	7	3	8	4	6
N8	4	4	8	6	6	4

若要判斷 N2 是否支配 N3，從中挑取 (CPU, RAM, HDD, HDD S., Q.) 這 5 個屬性比較，得到 N2 勝過於 N3。最後可以發現到 N2 這產品可以支配 N1, N3, N5, N6, N8。

現在問題來了，要找到不被任何產品支配的產品 (k-dominant skyline)。如上表 8 項產品的情況，只會有 N2, N4。

輸入說明

第一行會有一個整數 $T$ 表示有多少組測資。

每一組測資第一行會有三個整數 $N, \; D, \; K$，分別表示產品數量、產品屬性種類、以及支配比較的屬性種類。接下來會有 $N$ 行數據，每一行上會有 $D$ 個整數 $s_j$ 表示一個產品的屬性，產品按照輸入順序編號。

$N < 1024$
$0 < D, K < 8$
$0 < s_j < 1000$

輸出說明

對於每組測資輸出一行，輸出該組測資所有的 k-dominant skyline 的產品編號，由小到大輸出。若不存在則輸出 NONE。

範例輸入 #1

4

2 3 1
20 20 20
20 20 20

2 5 1
20 5 20 20 20
5 20 20 20 20

4 6 5
9 4 9 7 7 9
9 7 9 6 5 4
9 6 9 8 3 3
1 2 3 9 2 2

8 6 5
3 3 5 6 6 8
9 4 9 7 7 9
8 4 7 9 2 7
5 6 8 9 5 9
9 7 9 6 2 4
6 6 6 5 3 5
5 7 3 8 4 6
4 4 8 6 6 4

範例輸出 #1

Case #1: 1 2
Case #2: NONE
Case #3: 1
Case #4: 2 4

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (40%): 1.0s , <1M
公開測資點#1 (30%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (10%): 1.0s , <1M

提示：

標籤:

搜索優化篩法

出處:

[管理者：

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」