题意描述
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时，不需要进行任何操作
整理上述情况后，得到差分数组的操作：
代码语言：javascript复制 d[2] =2;
d[Min 1]--;
d[Max k 1] ;
//因为sum一定属于[min 1,max k]，所以进行操作时也对sum进行了改变
//所以要进行下面两行的改变，将sum恢复原值
d[sum]--;
d[sum 1] ;最后从前往后，将差分数组相加一遍，取最小值即可
参考博客：1343D
AC代码
代码语言：javascript复制#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;
}
