[题解] AtCoder ABC 454 F. 差分 / 贪心
TAG: 差分, 贪心
题目链接: 点击此处打开题目
题目大意
给定一个长度为 \(N\) 的数组 \(A\) 和一个模数 \(M\)。每次操作可以选择一个区间 \([l, r]\)，将区间内所有的 \(A_i\) 修改为 \((A_i + 1) \bmod M\)。
问最少需要多少次操作，才能使整个序列变成回文序列。
核心思路
1. 先只关心对称位置的差
因为最终目标是让数组变成回文，即 \(A_i = A_{N+1-i}\)，因此我们只需要关心对称位置上的差值。
我们可以构造一个长度为 \(\lfloor N/2 \rfloor\) 的数组 \(b\)，其中 \(b_i\) 表示第 \(i\) 对对称位置之间的差值（模 \(M\)）。
最终的目标就是通过最少的操作，让所有的 \(b_i = 0\)。
2. 原题操作等价于对 b 做区间加减
考虑原题的一次区间操作：
- 如果操作只落在左半边，那么对应 \(b\) 数组中某一段区间的整体 \(+1\)（或者 \(-1\)，取决于定义方向）。
- 如果操作只落在右半边，对应 \(b\) 数组中某一段区间的整体 \(-1\)。
- 如果操作跨域中心，相当于左半边一段前缀和右半边一段后缀分别受到了影响，本质上依然可以拆解为对 \(b\) 数组进行的连续区间加减。
因此，问题转化为了：给定长度为 \(\lfloor N/2 \rfloor\) 的数组 \(b\)，每次可以选择一个连续区间，把整段 \(+1\) 或 \(-1\)（模 \(M\)），最少多少次把它变成全 \(0\)。
3. 用差分把“区间操作”变成“单点操作”
对于区间加减操作，一个非常自然的思路是差分。我们定义差分数组 \(d\)，其中 \(d_i = (b_i - b_{i-1}) \bmod M\)。
这样，一次对 \(b[l \dots r]\) 的整体加减，只会影响两个位置：\(d_l\) 和 \(d_{r+1}\)。
具体来说：
- 要么是 \(d_l\) 增加 \(1\)，\(d_{r+1}\) 减少 \(1\)
- 要么是 \(d_l\) 减少 \(1\)，\(d_{r+1}\) 增加 \(1\)
所以问题进一步简化为：每次操作可以在差分数组 \(d\) 中任选两个位置，让一个位置 \(+1\)，另一个位置 \(-1\)（都在模 \(M\) 意义下）。我们需要求出最少多少次操作让所有 \(d_i\) 变成 \(0\)。
4. 贪心策略：排序后扫一遍
对于每个 \(d_i\)，我们要将其变成 \(0\)，有两种方式：
- 一直减，直到 \(0\)，需要操作 \(d_i\) 次。
- 一直加，绕一圈加到 \(M\) 取模变为 \(0\)，需要操作 \(M - d_i\) 次（前提是 \(d_i \neq 0\)）。
我们需要把 \(d\) 数组划分成两部分：一部分选择“减到 0”，另一部分选择“加到 M”。
因为每一次操作必然是一个位置 \(+1\)，一个位置 \(-1\)，所以总的操作次数就是这两部分所需代价的最大值（即把所有的加法需求和减法需求进行两两配对，不够的部分可以和自身互相抵消操作，总次数由需求较大的一方决定）。
为了使得代价最小化，我们可以贪心。显然，\(d_i\) 越大的元素，越应该选择“加到 M”的策略，因为它直接减到 \(0\) 的代价太大了。
因此，我们可以将 \(d\) 数组从小到大排序，初始时假设所有元素都选择“直接减到 0”，然后扫一遍数组，从大到小依次将元素更改为“加到 M”的策略，每次动态更新答案，取可能的最小值即可。
复杂度分析
- 时间复杂度：每组数据主要的时间开销在于对差分数组 \(d\) 的排序，时间复杂度为 \(O(N \log N)\)。所有测试用例的 \(N\) 总和不超过 \(2 \times 10^5\)，完全可以通过。
- 空间复杂度：需要存储额外的数组 \(a, b, d\)，空间复杂度为 \(O(N)\)。
原理解析与 AC 代码
关键变量说明
b：记录对称位置差值的数组，长度为 \(\lfloor N/2 \rfloor\)。d：数组b的差分数组。curz(current zero)：当前选择“直接减到 \(0\)”策略的代价总和。curm(current M)：当前选择“加到 \(M\)”策略的代价总和。ans：记录枚举所有划分情况过程中的最小操作次数。
代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e5+5;
const int INF=0x3f3f3f3f3f3f3f3f;
int n,m;
int a[N],b[N],d[N];
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];// 1. 构造对称位置差值数组 b// b[i] 表示第 i 对对称位置之间的差值（模 m）。目标是让所有 b[i]=0。for(int i=1;i<=(n>>1);i++) b[i]=(a[i]-a[n+1-i]+2*m)%m;n>>=1;if(!n){ // 如果 N < 2 (即 N=1)，本身就是回文，操作 0 次cout<<0<<endl;return;}// 2. 构造差分数组 d// 补出 b[n+1]=0，因为整个 b 数组全变成 0 的条件等价于差分数组 d 全为 0b[n+1]=0;for(int i=1;i<=n+1;i++)d[i]=((b[i]-b[i-1])%m+m)%m;// 3. 排序，为贪心划分做准备// 较小的 d[i] 倾向于直接减去 d[i]，较大的 d[i] 倾向于加上 m-d[i]sort(d+1,d+n+2);int curz=0,ans=INF,curm=0;// 初始状态：假设所有的 d[i] 都采用“减去 d[i]”变为 0 的策略for(int i=1;i<=n+1;i++) curz+=d[i];// 从大到小枚举，依次将当前最大的元素切换到“加上 m-d[i]”的策略组for(int i=n+1;i>=1;i--){if(d[i]){ // 如果 d[i]=0，不需要变成 m，直接跳过切换，这是特判的原因curm+=(m-d[i]);curz-=d[i];}// 总操作次数是两边需求的较大值，取所有切分状态下的最小值ans=min(ans,max(curm,curz));}cout<<ans<<endl;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;cin>>t;while(t--) solve();return 0;
}