题面

题意

给定一个长度为 n 的数列，n 为偶数，保证每个元素在 [ 1 , k ] 之间

每次操作可以把某个位置的数字变成 [ 1 , k ] 内的任意数字

要求让这个数列满足：对于所有的 i ∈ [ 1 , n/2 ]，a[i] + a[n-i+1] 是一个定值

问最少的操作次数

解题思路

差分数组维护取某个值为定值时所需要的最少操作次数

令差分数组为 delta

每次取一组 a[i] 和 a[n-i+1] 处理

令 sum = a[i]+a[n-i+1] , maxn=max(a[i],a[n-i+1]) , minn=min(a[i],a[n-i+1])

分类讨论得到：

　　一、如果定值 x 在 [2,minn] 之间，即使将较大的数更改为1后，和也是大于x，说明此时这两个数都需要更改，所以这段区间的操作数+2

　　二、如果定值 x 在 [maxn+k+1,2*k] 之间，即使将较小的数更改为k后，和也是小于x，说明此时这两个数都需要更改，所以这段区间的操作数+2

　　三、如果定值 x 在 [minn+1,maxn+k] 之间且不等于 sum，能够做到只改变其中一个数就使得和等于x，所以这个范围内操作数+1

　　四、特殊处理，如果定值 x 等于 sum，不需要更改任何一个数，所以这个点的操作数不需要增加

综上，对于差分数组的标记，我们可以得到：

delta[2]+=2;
delta[minn+1]-=2;
//讨论 1
delta[maxn+k+1]+=2;
delta[2*k+1]-=2;
//讨论 2
delta[minn+1]++;
delta[maxn+k+1]--;
delta[sum]--;
delta[sum+1]++;//因为上面两步把sum位置加上了1，所以这里减去1
//讨论 3、4

对于 2*k+1 这个位置，是差分数组标记的结尾，可以选择不进行处理

所以整理得到：

delta[2]+=2;
delta[minn+1]--;
delta[maxn+k+1]++;
delta[sum]--;
delta[sum+1]++;

最后从 2 位置开始到 2*k 处理一遍差分数组即可

ans=delta[2];
for(int i=3;i<=2*k;i++)
{
    delta[i]+=delta[i-1];
    ans=min(delta[i],ans);
}

完整程序

(62ms/1000ms)

#include<bits/stdc++.h>
using namespace std;

int ar[200050],delta[400050]; //差分数组开2*k的空间

void solve()
{
    int n,k,sum,minn,maxn,ans;

    cin>>n>>k;
    memset(delta,0,(2*k+10)*sizeof(int)); //初始化到2*k即可（稍大）

    for(int i=1;i<=n;i++)
    {
        cin>>ar[i];
        if(i>n/2)
        {
            sum=ar[i]+ar[n-i+1];
            minn=min(ar[i],ar[n-i+1]);
            maxn=sum-minn;

            delta[2]+=2;
            delta[minn+1]--;
            delta[maxn+k+1]++;
            delta[sum]--;
            delta[sum+1]++;
        }
    }

    ans=delta[2];
    for(int i=3;i<=2*k;i++)
    {
        delta[i]+=delta[i-1];
        ans=min(delta[i],ans);
    }

    cout<<ans<<‘\n‘;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    for(int t=1;t<=T;t++)
        solve();
    return 0;
}

Codeforces 1343D - Constant Palindrome Sum （差分数组）

原文：https://www.cnblogs.com/stelayuri/p/12749332.html