前言

「算法题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 26 篇题解,更多题解关注 Somnia1337@力扣。

D. 回文数组

题目描述

输入一个长为 n 的数组,输出使其变得回文的最少操作次数。

在 1 次操作中,可以二选一:

  • 选择一个元素,对其增减
  • 选择相邻的两个元素,对其增减

输入输出示例

输入共 2 行,第 1 行含一个正整数 n,第 2 行含 n 个正整数 x

4
1 2 3 4

范围:

  • n
  • x

输出一个整数表示答案:

3

解释:

  • 第 1 次操作后:[2, 3, 3, 4]
  • 第 2 次操作后:[3, 3, 3, 4]
  • 第 3 次操作后:[4, 3, 3, 4],已经是回文

解题思路

双指针 ij 从两端向中间看,每次先用“操作 1”使 arr[i] == arr[j],然后看 arr[i+1]arr[j-1] 是否与它们同号,如果同号,可以将一部分操作改为“操作 2”,从而节约操作次数。

实现时,可以先一次遍历,更新 arr[i] -= arr[j],再次遍历时仅比较 arr[i]arr[i+1] 是否同号即可。

答案

本答案已经在 dotcpp 取得 AC:

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        int n = Integer.parseInt(in.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 预处理
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            arr[i] -= arr[j];
        }
        
        // 遍历前一半
        long ans = 0;
        for (int i = 0; i < n / 2; i++) {
            if (arr[i] == 0) continue;
            // 先用 "操作 1" 变 arr[i]
            ans += Math.abs(arr[i]);
            // 再看能否顺便变一下 arr[i+1]
            if (i + 1 < n / 2 && arr[i] > 0 == arr[i + 1] > 0) {
                arr[i + 1] = Math.abs(arr[i]) > Math.abs(arr[i + 1]) ? 0 : arr[i + 1] - arr[i];
            }
        }
        out.println(ans);
        
        out.flush();
        out.close();
    }
}