解题思路

本题是 $k$ 近邻分类（KNN，k-Nearest Neighbors）的实现题：拿已标记实例当样本，为每个待判定实例判定标记。

对照只从已标记、且类型 $t$ 与询问实例相同的服务实例中选。类型不同的实例指标再接近也不参与，待判定实例自身不进对照集合；若无同类型对照，该行直接判定为 $0$。

两个服务实例的五项指标偏差用加权曼哈顿距离度量，权重 $a,b,c,e,f$ 由输入第二行给出：

题目内容

本题要求实现 $k$ 近邻（KNN）判定：已有 $n$ 个带标记的训练实例，还要判定 $m$ 个实例的标记，每个待判定实例都用与它最接近的 $k$ 个训练实例来投票。

每个实例记录所属类型 $t$（$0$ 或 $1$）与五项指标：累计请求数 $w$、累计响应数 $r$、平均排队时延 $tw$、平均处理时延 $tr$、采样轮数 $y$。

一、对照范围与距离

• 对照只从训练实例中类型 $t$ 与待判定实例相同的实例里选。
• 输入给出五个权重 $a,b,c,e,f$，两个实例的距离为

$d$ 越小越近。

二、取近邻与判定

• 把对照实例按 $d$ 升序、编号 $id$ 升序排列，取前 $k$ 个作为近邻；对照不足 $k$ 个时全部取用。
• 近邻中标记 $0$ 与标记 $1$ 谁多就判谁；两数相等时，取 $d$ 最小的那个近邻的标记。
• 对照为空时，判定为 $0$，该行只输出 $0$。

输入描述

第一行三个整数 $n,m,k$，依次为训练实例数、待判定实例数、近邻个数上限。

第二行五个整数 $a,b,c,e,f$，为五项指标的权重。

接下来 $n$ 行，每行八个整数，描述一个训练实例：编号 $id$、类型 $t$、累计请求数 $w$、累计响应数 $r$、平均排队时延 $tw$、平均处理时延 $tr$、采样轮数 $y$、标记 $s$（$0$ 正常、$1$ 异常）。

再接下来 $m$ 行，每行七个整数，描述一个待判定实例：编号 $id$、类型 $t$、累计请求数 $w$、累计响应数 $r$、平均排队时延 $tw$、平均处理时延 $tr$、采样轮数 $y$。

约束

$1\le n\le 1000$

$1\le m\le 200$

$1\le k\le n$

$1\le a,b,c,e,f\le 100$

$1\le id\le 10^{9}$

$t\in\{0,1\}$

$0\le w,r\le 10^{9}$

$0\le tw,tr\le 10^{4}$

$0\le y\le 30$

$s\in\{0,1\}$

输出描述

输出 $m$ 行，第 $i$ 行对应第 $i$ 个待判定实例：先输出判定结果，再按取用顺序输出各近邻的编号，相邻两项之间用一个空格分隔；没有对照时该行只输出 $0$。

样例1

输入

5 1 3
1 1 2 2 1
1 0 10 10 5 5 2 0
2 0 12 10 5 6 2 1
3 0 10 20 5 5 8 0
4 1 10 10 5 5 2 1
5 0 30 10 20 5 2 1
6 0 10 10 5 5 2

输出

0 1 2 3

说明

待判定实例编号为 $6$，类型 $t=0$。训练实例中类型为 $0$ 的是 $1,2,3,5$；编号 $4$ 类型为 $1$，不参与。

各实例与该实例的距离：

• 编号 $1$：$d=1\times 0+1\times 0+2\times 0+2\times 0+1\times 0=0$，标记 $0$；
• 编号 $2$：$d=1\times 2+1\times 0+2\times 0+2\times 1+1\times 0=4$，标记 $1$；
• 编号 $3$：$d=1\times 0+1\times 10+2\times 0+2\times 0+1\times 6=16$，标记 $0$；
• 编号 $5$：$d=1\times 20+1\times 0+2\times 15+2\times 0+1\times 0=50$，标记 $1$。

按 $d$ 升序取前 $k=3$ 个，近邻为 $1,2,3$。其中标记 $0$ 有 $2$ 个、标记 $1$ 有 $1$ 个，判定为 $0$，输出 0 1 2 3。

样例2

输入

4 2 2
1 1 1 1 1
1 0 0 0 0 0 0 0
2 0 1 0 0 0 0 1
3 0 2 0 0 0 0 1
4 1 0 0 0 0 0 1
5 0 0 0 0 0 0
6 1 0 0 0 0 0

输出

0 1 2
1 4

说明

待判定实例编号为 $5$，类型 $t=0$，类型相同的训练实例只有 $1,2,3$，距离依次为 $0,1,2$。取前 $k=2$ 个，近邻为 $1,2$，标记分别为 $0$ 和 $1$，两数相等，取 $d$ 最小的近邻（编号 $1$）的标记，判定为 $0$，输出 0 1 2。

待判定实例编号为 $6$，类型 $t=1$，类型相同的训练实例只有编号 $4$，对照不足 $k=2$ 个，全部取用；该实例标记为 $1$，判定为 $1$，输出 1 4。