蓝桥杯-大衣的回文数组（差分）

蓝桥账户中心

问题描述

大衣有一个长度为 N 的数组 A。他可以对数组 A 进行以下操作：

• 选择任意两个整数 L,R(1≤L≤R≤N)，对于所有索引 L≤i≤R修改 Ai​:=Ai​+1。

大衣想让数组 A​ 是回文的，请找出满足要求的最小操作次数。

输入格式

第一行输入一个正整数 T 表示测试数据的组数。

接下来 TT 组测试数据每组输入两行：

• 第一行输入一个正整数 N 表示数组 A 的长度。
• 第二行输入 N 个整数 A1,A2,⋯,AN表示数组 A 的元素。

输出格式

对于每组测试数据，输出一个整数表示满足要求的最小操作次数，并换行。

样例输入

3
6
2 6 4 3 4 1
2
1 10
3
1 10 1

样例输出

2
9
0

思路：变异的差分模板，用差分的思路，记录前半部分和后半部分相减得到的权重，然后循环遍历差分数组，第i位权重减去第i-1位权重就是当前位需要操作的次数，i-1位操作的时候，要是i位需要操作，就能一起操作，假设i要操作5次，i-1也要操作5次，那么总共就是操作5次，如果i要操作5次，i-1要操作4次，那么总共就是4+1次。

1. 初始化和输入处理：

   • 首先，读取测试数据的组数 t。对于每组测试数据，读取数组的长度 n 以及数组 A 的 n 个元素 A[1], A[2], ⋯, A[n]。
   • 定义一个差分数组 dif，长度为 n+2 并初始化为全 0。差分数组用于记录对原数组进行操作时的变化量，这里数组长度设置为 n+2 是为了在后续计算时方便处理边界情况，避免越界。

2. 计算差分数组：

   • 遍历原数组的前半部分（索引从 1 到 n/2），对于每个索引 l，计算其对称位置 r = n - l + 1 处的元素与 l 处元素的差值。
   • 如果 A[l] > A[r]，说明需要对位置 r 及之后的元素进行操作，使得 A[r] 增加到与 A[l] 相等，因此将差值 A[l] - A[r] 记录在差分数组的 dif[r] 位置上。
   • 如果 A[l] < A[r]，则需要对位置 l 及之后的元素进行操作，使得 A[l] 增加到与 A[r] 相等，所以将差值 A[r] - A[l] 记录在差分数组的 dif[l] 位置上。

3. 计算最小操作次数：

   • 初始化操作次数 ans 为 0。
   • 遍历差分数组 dif（从索引 1 到 n），计算当前位置 i 的差分与前一个位置 i-1 的差分的差值 sum = dif[i] - dif[i-1]。这个差值 sum 表示为了使当前位置的元素达到回文数组的要求，相对于前一个位置额外需要进行的操作次数。
   • 如果 sum > 0，说明当前位置需要进行操作，将 sum 累加到操作次数 ans 中。

代码：

#include <iostream>
#include <vector>
#define int long long
using namespace std;
int t,n,a[10005];
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        vector<int> dif(n+2,0);
        for(int i=1;i<=n;++i)cin>>a[i];
        for(int l=1;l<=n/2;++l){
            int r=n-l+1;
            if(a[l]>a[r])dif[r]=a[l]-a[r];
            else if(a[l]<a[r])dif[l]=a[r]-a[l];
        }
        int ans=0;
        for(int i=1;i<=n;++i){
            int sum=dif[i]-dif[i-1];
            if(sum>0)ans+=sum;
        }
        cout<<ans<<'\n';
    }
  return 0;
}