CF1986E.Beautiful Array

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个整数数组 $a_1, a_2, \ldots, a_n$ 和一个整数 $k$ 。你需要通过最少的操作次数使数组变得“美丽”。

在进行操作之前，你可以任意打乱数组元素的顺序。每次操作，你可以执行以下操作：

选择一个下标 $1 \leq i \leq n$ ，
令 $a_i = a_i + k$ 。

如果数组 $b_1, b_2, \ldots, b_n$ 满足对于所有 $1 \leq i \leq n$ ，都有 $b_i = b_{n - i + 1}$ ，则称该数组是“美丽的”。

请你求出使数组变得美丽所需的最少操作次数，或者报告无解。

输入格式

每组测试数据包含多组输入。第一行包含一个整数 $t$ （ $1 \leq t \leq 10^4$ ），表示测试数据组数。接下来是每组测试数据的描述。

每组测试数据的第一行包含两个整数 $n$ 和 $k$ （ $1 \leq n \leq 10^5$ ， $1 \leq k \leq 10^9$ ），分别表示数组 $a$ 的长度和题目中的整数 $k$ 。

每组测试数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \leq a_i \leq 10^9$ ），表示数组 $a$ 的元素。

保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

输出格式

对于每组测试数据，输出使数组变得美丽所需的最少操作次数。如果无解，输出 $-1$ 。

输入输出样例

输入#1

11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5

输出#1

说明/提示

在第一组测试数据中，数组已经是美丽的。

在第二组测试数据中，你可以在操作前打乱数组，然后对下标 $i = 1$ 执行 $83966524$ 次操作。

在第三组测试数据中，你可以先将数组 $a$ 打乱为 $[2, 3, 1]$ ，然后对下标 $i = 3$ 执行一次操作，得到数组 $[2, 3, 2]$ ，此时数组是美丽的。

在第八组测试数据中，无论如何操作和打乱元素，都无法使数组变得美丽。

在第九组测试数据中，数组已经是美丽的。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页