找出相似度最高的文档

[编程题]找出相似度最高的文档

热度指数：176 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

为了更快追踪突发热点，我们仅在“查询时刻 t 之前的最近 K 篇文档”内计算 TF‑IDF，并以加权余弦相似度挑选最相关的文档。

窗口内越新的文档权重越高（从旧到新第 j 篇的权重为 (K−j+1)/K）。

给定按时间递增的文档序列和若干查询（每条查询含时间点 t 与查询短语 q），请在窗口中找出与 q 的加权余弦相似度最高且相似度≥0.6 的文档编号；若存在并列最高，返回窗口中最早的那一篇；若无满足阈值的文档，输出 -1。

词向量用 TF‑IDF：TF 为词频；IDF 采用平滑公式 IDF(x)=log((N+1)/(df(x)+1))+1，其中 N 为窗口文档数，df(x) 为窗口内包含词 x 的文档数。
余弦相似度采用 q 与每个文档向量的点积除以范数乘积；文档向量还需乘以其时间权重。
文档与查询均以空格分词、统一小写，不做额外清洗。为避免早期窗口不足的问题，测试均保证 t ≥ K−1。

输入描述:

第一行：文档总数 N  
接下来 N 行：按时间从 0 到 N−1 的文档内容（小写，空格分词）  
下一行：窗口大小 K  
下一行：查询总数 P  
接下来 P 行：每行“t 空格 q”表示在时间点 t 的查询 q

输出描述:

输出 P 个数字，空格分隔；每个数字是对应查询的文档编号或 -1

示例1

输入

5
breaking news finance market
sports football world cup
finance stock market rises
tech ai model training
finance market crash report
3
3
4 finance market
5 ai model
3 travel guide

输出

4 3 -1

说明

对 t=4，窗口为文档[2,3,4]。q="finance market" 与 2、4 的原始余弦相似度相同且约为 0.605≥0.6；时间权重越新越大（2:1/3, 3:2/3, 4:1），加权后 4 更高，返回 4。
对 t=5，窗口为[2,3,4]。q="ai model" 仅与文档3匹配（含 ai、model），原始余弦≈0.707≥0.6，返回 3。
对 t=3，窗口为[1,2,3]。q="travel guide" 窗口内均无重合词，余弦=0<0.6，返回 -1。