题目描述
（英文不好请见谅）
给定一个有\(n\)个数的序列\(a\) (保证\(n\)为\(2\)的倍数)
给定一个整数\(k\)并保证保证\(1<=a_i<=k\)
现在可以将任意的\(a_i\)替换为\(1\)到\(k\)中的任意值，问使得对\(1<=i<=n/2\)都有\(a_i+a_{n-i+1}=x\)\(x\)为一正常数，需要最少次替换。
首先思路应该还是比较明确的，对于每一组都有三种可能
一个都不换。此时\(a_i+a_{n-i+1}=x\)必然不用换
只换一个。此时这一对的取值可以取遍\([min(a_i,a_{n-i+1})+1,max(a_i,a_{n-i+1})+k]\)
否则都需要将两个全部换掉才能满足题目要求。
不嫌丢人，先给大家看一看鄙人的暴力代码
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200005];
int inmin[200005];//我甚至做了小小的常数优化，当然并没有实际作用
int inmax[200005];
int insum[200005];
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
int t;
scanf("%d", &t);
while (t--)
{
int n, k;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int j = 1; j <= n / 2; j++)
{
inmin[j] = min(a[j], a[n - j + 1]) + 1;
inmax[j] = max(a[j], a[n - j + 1]) + k;
insum[j] = a[j] + a[n - j + 1];
}
int ans = 0xfffffff;
for (int tar = 2; tar <= 2 * k; tar++)
{
int cnt = 0;
for (int j = 1; j <= n / 2; j++)
{
if (insum[j] != tar)
{
if (tar >= inmin[j] && tar <= inmax[j])
{
cnt++;
}
else
{
cnt += 2;
}
}
}
ans = min(ans, cnt);
if (ans == 0)
break;
}
printf("%d\n", ans);
}
return 0;
}
这一组数据的时间复杂度高达\(O(nk)\)必然是没有办法过的。
我们就需要另辟蹊径去寻找一个更低时间复杂度的方法，有没有什么提示呢？我们还是从目标本身出发。也就是\(x\)的取值，这一波的遍历是不可避免的，那也就是说我们只能在对每一个\(x\)确定下来的时候的查询入手。这样的查询过程其实并不复杂。就如我在前文中说的，每一对只会有三种情况，并且三种情况的取值是连续但独立的。再说清楚一点其实就是对于每一对取值，他需要达到一个确定\(x\)值时需要的操作数是固定且连续分布的。
而我们又可以简单的查询到这样的分界点。那么就可以发挥上差分数组的优势了
我们可以以很快的速度来实现对一个数组的赋值，因为只需要在分界点处改变值就可以实现了对后续所有差分节点的更改。
如果你对差分数组尚不了解。可以点击这里
那么以下就是ac代码
/*
* @Author: Gehrychiang
* @LastEditTime: 2020-04-22 22:52:57
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
* @ProbTitle: Constant Palindrome Sum
*/
//差分数组才是正确做法
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200005];
int delta[400005]; //差分数组，与前缀和不同的是这里每一个其实保存着前一项与后一项之差，要还原只需从前向后累加即可
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
memset(delta, 0, sizeof(delta));
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n / 2; i++)
{
//显然我此时能够覆盖完全的范围为
//min(a[j], a[n - j + 1]) + 1至max(a[j], a[n - j + 1]) + k只替换一次
delta[2] += 2;
delta[min(a[i], a[n - i + 1]) + 1]--;
delta[a[i] + a[n - i + 1]]--;
delta[a[i] + a[n - i + 1] + 1]++;
delta[max(a[i], a[n - i + 1]) + k + 1]++;
}
int ans = (1 << 30);
for (int i = 2; i <= 2 * k; i++)
{
delta[i] += delta[i - 1];
ans = min(ans, delta[i]);
}
cout << ans << endl;
}
return 0;
}
类似还有一道好题牛妹吃豆子也是通过差分数组去进行维护以达到较低的时间复杂度