CF1986E Beautiful Array 题解

Part1. 题目概述

你有一个数组，其顺序可以随意打乱。

你可以在其中任选一个数增加 $k$，这记为一次操作。

求最小的操作次数以使原数组为回文串。

若不可能，输出 $-1$。

Part2. 思路

1. 首先看到只能增加 $k$，说明无论怎么操作，每个数除以 $k$ 的余数不变。

2. 要求得到回文串且顺序可以随意打乱，也就是说只要满足最终的数组只有不大于一个数出现的次数为奇数（这个数拿一个放中间，其他的左右两边对称放）。

3. 再回到1，除以 $k$ 的余数不变，那么可以对除以 $k$ 的每一个余数分组，每一组都可以通过加 $k$ 使得数字相等，比如这组样例的分组：

   1 2	13 3 2 3 9 14 17 10 22 20 18 30 1 4 28

   余数为 $0$	余数为 $1$	余数为 $2$
   $3,9,18,30$	$10,22,1,4,28$	$2,14,17,20$

4. 如何判断是否可行呢？只需要统计所有组中有几组的元素个数为奇数（如上面的分组中余数为 $1$ 组就是奇数个数，必须把这个组中的某个元素放到新序列的中心位置），如果个数大于 $1$，就一定是不可行的（不可能把多个元素放到中心）。

5. 接下来开始构造最优解。可以很清楚地发现，要在每一组中构造出相等的元素对（一个放前面，一个放后面），比如上余数为 $1$ 组可以这样构造：
   $$(2,14),(17,20)$$
   只要：
   $$(2+3\times4,14),(17+3\times1,20)$$
   进行了 $4+1=5$ 次操作。

   如果是奇数个元素的组，只需要取出一个元素放在中心后，变成偶数个元素的组即可。

6. 如何使解最优呢？可以先尝试把每一个组内排个序：

   余数为 $0$	余数为 $1$	余数为 $2$
   $3,9,18,30$	$1,4,10,22,28$	$2,14,17,20$

   这时候要分类讨论一下了：

   • 一组中有偶数个元素。

     从小到大，每次取两个，一定最优。（否则如果跨过中间的元素找，一定会需要更多操作，你可以自己模拟一下）。

   • 一组中有奇数个元素。

       很快想到朴素方法：枚举要去除的元素，求出去除每个元素下的最优，时间复杂度 $O(n^2)$。
     

     这显然会超时，但大致思路是可行的，求出下一个解时很多计算是和上一个重复的，这就有了优化的方法。下图七个数的情况：

     不取	第一组	第二组	第三组
     $1$	$(2,3)$	$(4,5)$	$(6,7)$
     $2$	$\color{red}(1,3)$	$(4,5)$	$(6,7)$
     $3$	$\color{red}(1,2)$	$(4,5)$	$(6,7)$
     $4$	$(1,2)$	$\color{red}(3,5)$	$(6,7)$
     $5$	$(1,2)$	$\color{red}(3,4)$	$(6,7)$
     $6$	$(1,2)$	$(3,4)$	$\color{red}(5,7)$
     $7$	$(1,2)$	$(3,4)$	$\color{red}(5,6)$

     红色的就是变化的部分，这样就解出了（分奇偶讨论一下）。
     $$f(a_{i+1})= \begin{cases}f(a_i)-\dfrac{(a_{i+2}-a_{i+1})}{k}+\dfrac{(a_{i+2}-a_i)}{k},\quad &&i \equiv 1 \pmod 2\f(a_i)-\dfrac{(a_{i+1}-a_{i-1})}{k}+\dfrac{(a_{i}-a_{i-1})}{k},\quad&&i \equiv 0 \pmod 2\end{cases} $$
     问题解决！

Part3. Code

注意数据范围，存余数等可以开映射解决，也可以离散化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include<bits/stdc++.h>
using namespace std;
int n,a[100001];
int mod[100001];
int k;
map<int,int>mds;
map<int,int>vis;
vector<int>modn;
map<int,vector<int> >md;
void solve(){
	cin>>n>>k;
	mds.clear();
	md.clear();
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mod[i]=a[i]%k;
		mds[mod[i]]+=1;
		md[mod[i]].push_back(a[i]);
	}
	vis.clear();
	modn.clear();
	int	ss=0;
	for(int i=1;i<=n;i++){
		if(vis[mod[i]]==0){
			modn.push_back(mod[i]);
			if(mds[mod[i]]%2)ss++;
			vis[mod[i]]=1;
		}
	}
	if(ss>=2){
		cout<<-1<<endl;
		return;
	}
	int sum=0;
	for(auto i:modn){
		sort(md[i].begin(),md[i].end());
		if(md[i].size()%2){
			int ss=0,s=0x3f3f3f3f;
			for(int j=1;j+1<md[i].size();j+=2){
				ss+=(md[i][j+1]-md[i][j])/k;
			}
			s=ss;
			for(int j=0;j+1<md[i].size();j++){
				if(j%2){
					ss=ss-(md[i][j+1]-md[i][j-1])/k+(md[i][j]-md[i][j-1])/k;
				}
				else{
					ss=ss-(md[i][j+2]-md[i][j+1])/k+(md[i][j+2]-md[i][j])/k;
				}
				s=min(s,ss);
			}
			sum+=s;
		}
		else{
			for(int j=0;j+1<md[i].size();j+=2){
				sum+=(md[i][j+1]-md[i][j])/k;
			}
		}
	}
	cout<<sum<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}