- 小信的数组元素和
题目ID：20684必做题100分
时间限制: 1000ms
空间限制: 262144kB
题目描述
小信有一个长度为偶数
n
n的数组
a
a，所有元素
a
i
a
i
的大小都不超过
k
k。
小信每次可以选择某个元素将其替换为
[
1
,
k
]
[1,k]之间的任意一个整数，使得满足对于所有
[
1
,
n
2
]
[1,
2
n
]的下标
i
i，有：
a
i
+
a
n
−
i
+
1
x
a
i
+a
n−i+1
=x，这里
x
x对于所有
n
2
2
n
对元素都应该是相等的。
小信想知道他应该最少操作多少次才能满足以上条件。
输入格式
多组输入，第一行输入一个整数
t
(
1
≤
t
≤
10
)
t(1≤t≤10)，表示测试数据的组数。
对于每组测试数据，第一行输入两个整数
n
n和
k
(
2
≤
n
≤
2
×
1
0
4
,
1
≤
k
≤
2
×
1
0
4
)
k(2≤n≤2×10
4
,1≤k≤2×10
4
)，分别表示数组
a
a的长度和元素
a
i
a
i
的最大可取值，数据保证
n
n是偶数。
第二行输入
n
n个整数
a
1
,
a
2
,
.
.
.
,
a
n
(
1
≤
a
i
≤
k
)
a
1
,a
2
,…,a
n
(1≤a
i
≤k)。
输出格式
对于每组测试数据，一行输出一个整数表示小信的最少操作次数。
样例
Input 1
4
4 2
1 2 1 2
4 3
1 2 2 1
8 7
6 1 1 7 6 3 4 6
6 6
5 2 6 1 3 4
Output 1
0
1
4
2
样例解释
对于第一组测试数据，有：
a
1
+
a
4
3
,
a
2
+
a
3
3
a
1
+a
4
=3,a
2
+a
3
=3，两对都是相等的，小信无需操作。
对于第二组测试数据，小信可以把
a
1
1
a
1
=1修改成
a
1
3
a
1
=3，有：
a
1
+
a
4
3
+
1
4
a
1
+a
4
=3+1=4，
a
2
+
a
3
2
+
2
4
a
2
+a
3
=2+2=4，小信最少操作一次即可。
#include <bits/stdc++.h>
using namespace std;
int t;
int main()
{
// freopen("uoj1.in","r",stdin);
// freopen("uoj1.ans","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
int n,k,A[20005],minn=INT_MAX,maxx,ans=INT_MAX;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>A[i];
minn=min(minn,A[i]);
}
maxx=minn+k;
for(int x=2;x<=maxx;x++)
{
int cnt=0;
for(int i=1;i<=n/2;i++)
{
if(A[i]+A[n-i+1]!=x)
{
if((x-A[i]>=1&&x-A[i]<=k)||(x-A[n-i+1]>=1&&x-A[n-i+1]<=k)) cnt++;
else {cnt=INT_MAX;break;}
}
}
ans=min(ans,cnt);
}
cout<<ans<<'\n';
}
return 0;
}