codeforces 1343D（差分数组）

题意描述

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

AC代码

#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;
}