CF1343D Constant Palindrome Sum 题解

Andrewzdm · 2020-04-22 12:54:10 · 题解

也许更好的阅读体验

CF1343D Constant Palindrome Sum

打比赛的时候这道题没想出来，等到想出来的时候比赛结束了……qwq

下面进入正题：（前一部分我会复盘我的思路过程供大家参考，当然这是一个蒟蒻的思考过程， 大家完全可以跳过）

首先拿到题目，先想了下能否贪心，发现找不到贪心策略。毫无头绪，我开始尝试寻找突破口。这时我发现题目有一点比较奇怪：题目给了 k 的范围还保证 \sum k \leq 2 \times 10^5。这就在暗示我们复杂度正常情况下应该含有 k（大部分题目还是没有废话的）。

接下来我观察到因为所有的数（初始的和替换的）都在 [1,k] 内，所以每一对数的和一定在 [2,2k] 内。

那么我们不妨考虑枚举题目中要求的等式

中的 x(2 \le x \le 2k)，算出每一对数需要替换多少个数，最后在所有的结果中取 \min，时间复杂度为 O(nk)。

但是这样会 \texttt{TLE}，为了不超时，基于枚举 x 的算法思想，时间复杂度要么 O(k \log n) 要么 O(k+n)。

首先我想出了一个解法，然而很遗憾是错的。这个想法是这样的（不想看的可以跳过）：
把每一对数的总和进行排序，然后把所有的总和分成 sum<x,sum=x,sum>x 三个部分。当 2 \le x \le k 时，除了 sum=x 的一部分，剩下的两部分都要进行一次替换。还没开始想 k < x \le 2k 的情况，我就发现我错了：

比方说给定的 a 是 1,2,2,3，求出总和排序后是 4,4。当 x=2 时，我们会计算出替换次数为 2。可是 2,2 这一对数要想总和为 2 必须替换两次。所以替换次数应该为 3。

好吧，只能换思路了。

接下来是正解：

我们先前的算法之所以是 O(nk)，是因为我们在枚举 x 的过程中才计算每一对数需要替换多少个。为了优化，我们需要想办法进行预处理，算出对于每一个 x，有多少对数可以一个都不替换，有多少可以只替换其中一个，有多少必须两个都要替换。

不妨考虑各个击破：

一个都不替换

这个很简单，我们开一个数组 equ，其中 equ_i 表示当 x=i 时有多少对数可以一个都不替换。 因为不用替换的条件就是一对数的和 sum=x，那么我们只要算出每一对数的和 sum，并且 equ[sum]++ 就可以了。

只需要替换其中一个

首先，对于一对数 a_i,a_{n-i+1}，在只替换其中一个数的情况下，它们的和只能在 [\min(a_i,a_{n-i+1})+1, \max(a_i,a_{n-i+1})+k] 中。我们稍微变通一下，求出有多少对数至多需要替换一个，那么只需要替换一个的数目就很好求了，为至多需要替换一个的数目减去一个都不需要替换的数目。

那么如何求出有多少对数至多需要替换一个？这个问题就变成了：对于 x，求出有多少个区间 [\min(a_i,a_{n-i+1})+1, \max(a_i,a_{n-i+1})+k] (1 \le i \le \dfrac{n}{2}) 覆盖了 x。

这一问题可以这样解决（而且对于类似的“求每一个数有多少个区间覆盖了此数”的问题都可以这样做）：
开一个数组 cover，cover_i 表示有多少个区间覆盖了数 i。首先枚举区间，设区间的左右端点分别为 l,r，然后我们进行操作 cover[l]++ 和 cover[r+1]--，枚举完后再用计算前缀和的方式进行如下操作： cover[i] += cover[i-1]。然后我们就求完了。

下面解释下算法的原理：其实我们 cover[l]++ 和 cover[i] += cover[i-1] 的两个操作等效于对于所有的 i \in [l,rbound] 进行 cover[i]++。类似的，我们也进行了 cover[i]--(i \in [r+1, rbound])。前一个操作计算了有多少个区间的左端点小于等于 x，而后一个操作计算了有多少个区间的右端点小于 x。一加一减就是覆盖了 x 的区间数目。

如果还是难以理解，可以尝试自己举个栗子模拟一下，这里就不赘述了。

两个都需要替换

因为我们求出了 cover，这一问题相当简单。一句话搞定：

不要忘了我们的 cover_i 表示有多少对至多需要替换一个数。

所以我们对于每个 x，最少替换步数 ans_x 就可以这样计算：

最终时间复杂度 O(k+n)。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int equ[2 * maxn], cover[2 * maxn], a[maxn];

signed main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        for(int i = 1; i <= n; i++)
            scanf("%d", a + i);
      //注意值域最大为2k，初始化到2k+4比较保险。
        fill(equ, equ + 2 * k + 5, 0);
        fill(cover, cover + 2 * k + 5, 0);
        for(int i = 1; i <= n / 2; i++)
            equ[a[i] + a[n - i + 1]]++;
        for(int i = 1; i <= n / 2; i++)
        {
            cover[min(a[i], a[n - i + 1]) + 1]++;
            cover[max(a[i], a[n - i + 1]) + k + 1]--;//注意加上k之后还要加上1
        }
        for(int i = 3; i <= 2 * k; i++)//值域最小为2，所以从3开始做前缀和就可以了
            cover[i] += cover[i - 1];
        int ans = INT_MAX;
        for(int x = 2; x <= 2 * k; x++)
            ans = min(ans, cover[x] - equ[x] + (n / 2 - cover[x]) * 2);//这里就没有再开一个数组num了
        printf("%d\n", ans);
    }
    return 0;
}