You are given an array a consisting of n integers (it is guaranteed that n is even, i.e. divisible by 2). All ai does not exceed some integer k.
Your task is to replace the minimum number of elements (replacement is the following operation: choose some index i from 1 to n and replace ai with some integer in range [1;k]) to satisfy the following conditions:
after all replacements, all ai are positive integers not greater than k; for all i from 1 to n2 the following equation is true: ai+an−i+1=x, where x should be the same for all n2 pairs of elements. You have to answer t independent test cases.
可以将 a [ i ] 和 a [ n − i + 1 ] a[i]和a[n-i+1] a[i]和a[n−i+1]变成[ 1 : k 1:k 1:k]范围内的任意数字,求使 a [ i ] + a [ n − i + 1 ] = x a[i]+a[n-i+1]=x a[i]+a[n−i+1]=x的最小变化次数
考虑维护一个差分数组 d [ i ] d[i] d[i],表示定值为 i i i时的操作次数。令 m a x = m a x ( a [ i ] , a [ n − i + 1 ] ) max=max(a[i],a[n-i+1]) max=max(a[i],a[n−i+1]), s u m = a [ i ] + a [ n − i + 1 ] sum=a[i]+a[n-i+1] sum=a[i]+a[n−i+1], m i n = m i n ( a [ i ] , a [ n − i + 1 ] ) min=min(a[i],a[n-i+1]) min=min(a[i],a[n−i+1]) 分情况讨论后发现: 1. 1. 1.当定值位于 [ 2 , m i n ] [2,min] [2,min]之间时,在这种情况下,需要两次操作 2. 2. 2.当定值位于 [ m i n + 1 , m a x + k ] [min+1,max+k] [min+1,max+k]之间时,在这种情况下,只需要一次操作 3. 3. 3.当定值位于 [ m a x + k + 1 , 2 k ] [max+k+1,2k] [max+k+1,2k]之间时,在这种情况下,需要两次操作 4. 4. 4.当定值正好等于 s u m sum sum时,不需要进行任何操作
整理上述情况后,得到差分数组的操作:
d[2]+=2;
d[Min+1]--;
d[Max+k+1]++;
//因为sum一定属于[min+1,max+k],所以进行操作时也对sum进行了改变
//所以要进行下面两行的改变,将sum恢复原值
d[sum]--;
d[sum+1]++;
最后从前往后,将差分数组相加一遍,取最小值即可
参考博客:1343D
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long ll;
const int N=2*1e5+10;
const int M=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int a[N],d[N*2];
void solve(){
int n,k;cin>>n>>k;
rep(i,0,2*k+10) d[i]=0;
rep(i,1,n+1) cin>>a[i];
int Min=1e9+7,Max=0;
rep(i,1,n/2+1){
int sum=a[i]+a[n-i+1];
Min=min(a[i],a[n-i+1]);
Max=max(a[i],a[n-i+1]);
d[2]+=2;
d[Min+1]--;
d[Max+k+1]++;
d[sum]--;
d[sum+1]++;
}
int ans=d[2];
rep(i,3,2*k+1){
d[i]+=d[i-1];
ans=min(ans,d[i]);
}
cout<<ans<<endl;
}
int main(){
IOS;
int t;cin>>t;
while(t--){
solve();
}
return 0;
}