CF-636D Constant Palindrome Sum 题解

题目大意

给你n个不超过k的数（n为偶数），要求a[i]+a[n-i+1]都等于一个数x，你可以替换任意一个数，使其变成1到k中任意一个数，问你最少替换多少个数，使数组满足条件。

解题思路

（我写到这里用了45分钟，后面就动不了了。。。我还是太菜了。。

我是没想到用差分。。

用一个数组d[i]来表示，x为i时，需要替换多少个数字。

令sum=a[i]+a[n-i+1]，maxn=max（a[i]，a[n-i+1]），minn=min（a[i]，a[n-i+1]）。

我们取极端情况，当大的那个数字为1时，在修改一个数字的时候，和最小，为minn+1。

当小的那个数字为k时，在修改一个数字的时候，和最大，为maxn+k。

所以

1、x在[2,minn]时，需要修改两个数字，d[2]+=2，d[minn+1] -=2。

2、x在[minn+1,maxn+k]时，需要修改一个数字，d[minn+1]++，d[maxn+k+1]- -。

3、x在[maxn+k+1,2 * k]时，需要修改两个数字，d[maxn+k+1]+=2，d[2 * k+1]-=2（这个可以不用）。

4、x为sum时，不需要修改，但是sum在第二种情况中已经被修改了，所以需要补上来 ，d[sum]- -，d[sum+1]++。

整理后

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

然后从2到2*k跑一边差分取最小值即可。

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 2e5 + 5;
int num[N],d[2*N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	int n,k;
	while (t--) {
		memset(d, 0, sizeof(d));
		cin >> n >> k;
		int sum, maxn, minn;
		for (int i = 1; i <= n; i++) {
			cin >> num[i];
			if (i > n / 2) {
				sum = num[i] + num[n - i + 1];
				maxn = max(num[i], num[n - i + 1]);
				minn = min(num[i], num[n - i + 1]);
				d[2] += 2;//差分
				d[minn+1]--;
				d[maxn + k + 1]++;
				d[sum]--;
				d[sum + 1]++;
			}
		}
		int ans = 1e9;
		for (int i = 2; i <= 2 * k; i++) {
			d[i] += d[i - 1];
			ans = min(ans, d[i]);
		}
		cout << ans << '\n';
	}
}