题目分析

给定一个整数数组，我们需要通过一系列操作将其变成回文数组。每次操作可以选择两个相邻元素，增加它们的值。目标是计算至少需要多少次操作使得数组变成一个回文数组。如果不可能实现，则返回-1。

回文数组的定义是：该数组从左到右和从右到左完全相同。

思路

1. 对称性：要使一个数组成为回文数组，数组的左右两侧必须对称。即对于每一对元素，a[i] 和 a[n-i-1]，它们的值必须相等。

2. 操作方式：每次我们可以选择两个相邻元素增加其值。设定一个操作对两个相邻元素 a[i] 和 a[i+1] 进行增加，即 a[i] = a[i] + x 和 a[i+1] = a[i+1] + x，这样可以改变这些元素的大小，逐渐使其变得对称。

3. 策略：我们从数组的两端开始，逐步比较并调整不相等的元素。每次如果发现 a[i] 和 a[n-i-1] 不相等，就将较小的元素增加，直到它们相等。这个操作的核心是通过最少的次数使得两边的元素逐渐接近。

4. 终止条件：如果两边的元素在经过若干次操作后能够相等，那么可以继续；否则如果无法通过加法使它们相等，那么就返回 -1。

5. 最优策略：每次操作都尽量增大最小的元素，这样可以保证最少的操作次数。

具体操作

1. 从数组的两端开始，比较对称位置的元素。
2. 如果不相等，选择较小的元素进行加法操作，直到它们相等。
3. 记录每次操作的过程，并确保操作次数最小。

时间复杂度

由于我们需要一次遍历数组进行操作，时间复杂度为 O(n)，其中 n 是数组的长度。每次操作只涉及两元素的加法，因此不会对算法的复杂度造成影响。

代码实现

Python 实现

def make_palindrome(n, arr):
    operations = []
    i, j = 0, n - 1
    
    while i < j:
        if arr[i] < arr[j]:
            diff = arr[j] - arr[i]
            arr[i] += diff
            arr[i + 1] += diff
            operations.append((i + 1, diff))  # 记录操作
        elif arr[i] > arr[j]:
            diff = arr[i] - arr[j]
            arr[j] += diff
            arr[j - 1] += diff
            operations.append((j, diff))  # 记录操作
        i += 1
        j -= 1
    
    # 检查是否是回文数组
    if arr == arr[::-1]:
        print(len(operations))
        for op in operations:
            print(op[0], op[1])
    else:
        print(-1)

# 输入读取
n = int(input())
arr = list(map(int, input().split()))
make_palindrome(n, arr)

Java 实现

import java.util.*;

public class Main {
    public static void makePalindrome(int n, long[] arr) {
        List<long[]> operations = new ArrayList<>();
        int i = 0, j = n - 1;
        
        while (i < j) {
            if (arr[i] < arr[j]) {
                long diff = arr[j] - arr[i];
                arr[i] += diff;
                arr[i + 1] += diff;
                operations.add(new long[]{i + 1, diff});
            } else if (arr[i] > arr[j]) {
                long diff = arr[i] - arr[j];
                arr[j] += diff;
                arr[j - 1] += diff;
                operations.add(new long[]{j, diff});
            }
            i++;
            j--;
        }
        
        // 检查是否是回文数组
        boolean isPalindrome = true;
        for (int k = 0; k < n / 2; k++) {
            if (arr[k] != arr[n - k - 1]) {
                isPalindrome = false;
                break;
            }
        }
        
        if (isPalindrome) {
            System.out.println(operations.size());
            for (long[] op : operations) {
                System.out.println(op[0] + " " + op[1]);
            }
        } else {
            System.out.println(-1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        makePalindrome(n, arr);
    }
}

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

void makePalindrome(int n, vector<long long>& arr) {
    vector<pair<int, long long>> operations;
    int i = 0, j = n - 1;

    while (i < j) {
        if (arr[i] < arr[j]) {
            long long diff = arr[j] - arr[i];
            arr[i] += diff;
            arr[i + 1] += diff;
            operations.push_back({i + 1, diff});
        } else if (arr[i] > arr[j]) {
            long long diff = arr[i] - arr[j];
            arr[j] += diff;
            arr[j - 1] += diff;
            operations.push_back({j, diff});
        }
        i++;
        j--;
    }

    // 检查是否是回文数组
    bool isPalindrome = true;
    for (int k = 0; k < n / 2; k++) {
        if (arr[k] != arr[n - k - 1]) {
            isPalindrome = false;
            break;
        }
    }

    if (isPalindrome) {
        cout << operations.size() << endl;
        for (auto& op : operations) {
            cout << op.first << " " << op.second << endl;
        }
    } else {
        cout << -1 << endl;
    }
}

int main() {
    int n;
    cin >> n;
    vector<long long> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    makePalindrome(n, arr);
    return 0;
}

题目内容

小红有一个整数数组，长度为$n$。她希望通过一系列操作将数组变成一个回文数组。每次操作可以选择数组中任意两个相邻的元素$a_i$和$a_{i+1}$，将它们的值同时加一。

请你计算至少需要多少次操作使得数组变成一个回文数组。如果不可能，则输出$-1$。否则输出具体的操作方案。

注意:回文数组指该数组从左到右与从右到左完全相同。

输入描述

第一行包含一个正整数$n(1≦n≦10^5)$，表示数组的长度。

第二行包含$n$个整数，表示数组的各个元素$a_i(1 ≦a_i≦10^9)$。

输出描述

如果不能通过操作使得数组变成回文数组，则输出$-1$。

否则先输出一个整数$m$，接下来$m$行，每行包含两个整数$i$和$x$，表示将$a$和$a_{i+1}$同时加$x$，表示进行了$x$次操作。 你需要保证$0≦m ≦n,x >0$，并且$\sum x$最小

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

3
1 3 2

输出

1
1 1

说明

可以对数组的前两个元素进行一次操作，使$1$变为$2$，$3$变为$4$，此时数组变为$[2,4,2]$，为回文数组。