CF1343 D. Constant Palindrome Sum

D. Constant Palindrome Sum

Question

给定一个长度为 $n$n 的数列， $n$n 为偶数，保证每个元素在 $[1,k]$[1,k] 之间。
每次操作可以把某个位置的数字变成 $[1,k]$[1,k] 内的任意数字。
要求让这个数列满足：对于所有的 $i\in [1,\frac{n}{2}]，a\left[i\right]+a[n-i+1]$i∈[1,2n​]，a[i]+a[n−i+1] 均相等为 $res$res。
求最少的操作次数。

Solution

差分维护修改次数
为了下列表述简单方便、简洁，设
$mi=min\left(a\right[i],a[n-i+1\left]\right)$mi=min(a[i],a[n−i+1])
$ma=max\left(a\right[i],a[n-i+1\left]\right)$ma=max(a[i],a[n−i+1])

1. 修改次数为0： $res=a\left[i\right]+a[n-i+1]$res=a[i]+a[n−i+1]。
2. 修改次数为1： $res\in [mi+1,ma+k]andres\ne a\left[i\right]+a[n-i+1]$res∈[mi+1,ma+k] and res​=a[i]+a[n−i+1]
3. 修改次数为2： $res\in [2,mi]\cup [ma+k+1,2k]$res∈[2,mi]∪[ma+k+1,2k]

直接暴力是 $O\left(nk\right)$O(nk)，考虑优化利用差分数组维护答案为 $[2,2k]$[2,2k]时的修改次数。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 4e5 + 5;

int n,k,a[N],d[N];

void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=2*k;i++) d[i]=0;
	for(int i=1;i<=n/2;i++){
		d[2]+=2;
		d[min(a[i],a[n-i+1])+1]--;
		d[a[i]+a[n-i+1]]--;
		d[a[i]+a[n-i+1]+1]++;
		d[max(a[i],a[n-i+1])+k+1]++;
	}
	int ans=n;
	for(int i=2;i<=2*k;i++){
		d[i]+=d[i-1];
		ans=min(ans,d[i]);
	}
	cout<<ans<<'\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;cin>>T;
	while(T--){
		solve();
	}
	return 0;
}