D. Constant Palindrome Sum(差分)

Problem - 1343D - Codeforces

题意:给你n(偶数)个不超过k的数,你可以改变其中任何一个并且用[1,k]的数代替,最后使1<=i<=n/2

ai + an-i+1 == 某个数x,问最多需要替换几个数

题解:

这题最大的疑问就是这个x究竟是什么,那既然我们不知道,我们就枚举x的范围[2,2*k]

然后让我们分一下情况

1.一个都不需要改变用cnt数组记录下,ai + an-i+1 出现的次数

2.需要改变一个

变化的值是有一范围的

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

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

min <= x <= max

定义一个f数组让范围内的值都加1,但是或遍历多次,所以要用到差分

3.需要改变两个,那么我们就结合到,最终遍历看

遍历2~2*k,(f[i]-cnt[i])+2*(n/2-f[i])

如果f[i]小于n/2的相等的元素,意味着剩下的都要改变两个

#include
#include
using namespace std;
int a[400050];
int cnt[400050];
int f[400050];
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n,k;
		cin >> n>> k;
		int ans = 1e9;
		for(int i = 1;i <= n;i++)
		{
			cin >> a[i];
		}
		for(int i = 1;i <= 2*k;i++)
		{
			cnt[i] = 0;
			f[i] = 0;
		}
		for(int i = 1;i <= n/2;i++)
		{
			cnt[a[i]+a[n-i+1]]++;
		}
		for(int i = 1;i <= n/2;i++)
		{
			int l = min(a[i],a[n-i+1]) + 1;
			int r = max(a[i],a[n-i+1]) + k;
			f[l]++,f[r+1]--;
		}
		for(int i = 1;i <= 2*k;i++)
		{
			f[i] = f[i-1] + f[i];
		}
		for(int i = 1;i <= 2*k;i++)
		{
			ans = min(ans,(f[i]-cnt[i])+2*(n/2-f[i]));
		}
		cout<"\n";
	}
}