全国信息学奥林匹克联赛（NOIP2016）复赛模拟试题 提高组 day2 第 5 页 共 6 页 Genius ACM 【问题描述】 Advanced CPU Manufacture r (ACM) is one of the best CPU manufacturers in the world. 每天, 该公司生产 𝑛 台 CPU 并销售到世界各地。 ACM 公司的质检部门会对生产出的 CPU 进行成组测试，对一组（若干个） CPU 进行测试的方法如下：

1. 随机从该组 CPU 中选取 𝑚 对（即 2𝑚 台） ，若总数不足 2𝑚 台，则 选取尽量多对。
2. 对于每一对 CPU，测量它们之间的 Relative Performance Difference
   (𝑅𝑃𝐷)，并把第 𝑖 对的𝑅𝑃𝐷记为 𝐷௜。𝑅𝑃𝐷的计算方法在后面给出。
3. 该组 CPU 的 Sqared Performance Difference (𝑆𝑃𝐷) 由以下公式给出： 𝑆𝑃𝐷 = ෍ 𝐷௜ ଶ ௜
4. 该组 CPU 通过质检，当且仅当 𝑆𝑃𝐷 ≤ 𝑘, 其中 𝑘 是给定常数。 ACM 公司生产的 CPU性能很好，而质检部门制定的标准更是过于严格。通 常他们把 𝑛 台 CPU 作为一整组进行测试，这导致一些性能良好的 CPU 无法通 过测试，生产部门对此颇有微词。作为质检部门的领导，小S 在不更改质检测试 流程的前提下，想出了这样一个主意：如果能够把 𝑛 台 CPU 恰当地分成连续的 若干段，使得每段 CPU都能够通过成组测试，就可以解决当下的问题。 现在，小 S 已经知道了𝑛 台各自的性能表现𝑃ଵ … 𝑃௡，两台 CPU 的𝑅𝑃𝐷被定 义为它们性能表现的差的绝对值。请你帮忙计算一下，至少把这些 CPU 分成多 少段，才能使得每一段都能通过成组测试。 【输入格式】 每个测试点包含多组数据，第一行一个整数 𝑇 给出数据组数。 对于每组数据，第一行三个整数 𝑛, 𝑚, 𝑘，第二行 𝑛 个整数 𝑃ଵ … 𝑃௡。 【输出格式】 对于每组数据，输出一个整数表示答案。 样例输入 样例输出 2 5 1 49 8 2 1 7 9 5 1 64 8 2 1 7 9 2 1 全国信息学奥林匹克联赛（NOIP2016）复赛模拟试题 提高组 day2 第 6 页 共 6 页 【数据规模与约定】 对于 20%的数据，1 ≤ 𝑛 ≤ 10 ଶ。 对于 40%的数据，1 ≤ 𝑛 ≤ 10 ଷ。 对于另外 10%的数据，𝑘 = 0。 对于另外 10%的数据，0 ≤ 𝑘 ≤ 1。 对于另外 10%的数据，𝑚 = 1。 对于另外 10%的数据，1 ≤ 𝑚 ≤ 2。 对于 90%的数据，0 ≤ 𝑘 ≤ 10ଵଶ。 对于 100%的数据，𝑇 ≤ 12, 1 ≤ 𝑛, 𝑚 ≤ 5 ⋅ 10 ହ, 0 ≤ 𝑘 ≤ 10ଵ଼, 0 ≤ 𝑃௜ ≤ 2ଶ଴。