D. Constant Palindrome Sum（差分数组维护）

Problem - D - Codeforces

题意：给定长度为n的数组，每次操作可以选择一个数令a[i]变成[1,k]范围内的一个数，问最少需要多少次操作可以让a[i]+a[n-i+1]==x (1<= i <= n/2)满足。

思路：利用差分数组d[i]表示x取i需要的总操作数。

枚举每一对数，计算x的取值范围及所需的操作数

记mi=min(a[i] , a[n-i+1])

ma=max(a[i] , a[n-i+1])

sum=a[i] + a[n-i+1]

修改一个数时，x取值范围为[mi+1, ma+k];修改两个数时，x的取值范围为[2,2k]

所以当x∈[mi+1, ma+k]，为达到x需要修改一次，即让[mi+1, ma+k]范围内的数都+1

当x∈[2,mi+1)∪(ma+k, 2k]，为达到x需要修改两次，即让[2,mi+1)∪(ma+k, 2k]范围内的数都+2

注意当x==sum时，不要操作

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,k;
int a[N],d[N];
void solve()
{cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];for(int i=0;i<=2*k;i++) d[i]=0;for(int i=1;i<=n/2;i++){int mi=min(a[i],a[n-i+1]);int ma=max(a[i],a[n-i+1]);int sum=a[i]+a[n-i+1];d[2]+=2;d[mi+1]--;d[sum]--;d[sum+1]++;d[ma+k+1]++;d[2*k+1]--;}for(int i=1;i<=2*k;i++)d[i]+=d[i-1];int ans=inf;for(int i=2;i<=2*k;i++)ans=min(ans,d[i]);cout<<ans<<'\n';
}
signed main()
{//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}