B站笔试 B站笔试题 bilibili 0518

笔试时间：2025年5月18日

第一题：对称数组

小红有一个数组，她每次可以让两个相邻的数字一起加一，她想知道把数组变成左右对称的最小操作次数。

左右对称的意思是将数组整体翻转后与原数组一致，例如:{1,2,3,3,2,1}，{4,0,4}都是左右对称的，而{8,1,0,9,7,5}，{9,2,2,7,6,8}都不是左右对称的。

输入描述

第一行输入一个整数 n(1 ≤n ≤ 2* 10^5)，表示数组长度。

第二行输入n 个整数 a¡ (0 ≤ a¡≤ 10^9)表示数组。

输出描述

输出一个整数表示将数组变成左右对称的最小操作次数，若无法变成左右对称，则输出-1.

样例输入

5

1 1 2 2 1

样例输出

1

说明：将第二个元素和第三个元素加一即可,{1,1+1 2+1,2,1} -> {1,2,3,2,1}。

参考题解

要将数组变成左右对称，我们需要确保数组中的元素满足 a[i] + a[n-1-i] 对于所有 i 从 0 到 n/2-1 都相等。每次操作可以选择两个相邻的元素同时加1，这会影响对称位置上的元素。关键在于如何通过这些操作调整对称位置上的元素之和。

检查可行性：首先，我们需要检查是否可以通过操作使得所有对称位置的和相等。具体来说，对于对称位置 (i, j)（其中 j = n-1-i），如果 i < j，那么这些位置的和必须满足一定的条件。特别是，对于相邻的对称对，比如 (i, i+1) 和 (j-1, j)，操作会影响这些对称对的和。但经过分析，可以发现，只要对称位置的和的差是偶数，就有可能通过操作调整。

计算操作次数：对于每个对称对 (i, j)，我们需要确定它们的和应该等于某个目标值。这个目标值通常由中间对称对决定。例如，对于数组长度为奇数的情况，中间元素可以单独处理。然后，通过贪心的方式，从外向内或从内向外调整对称对的和，确保每次操作都能有效减少差异。

贪心调整：从数组的两端向中间处理。对于每个对称对 (i, j)，计算当前和与目标和的差。如果当前和小于目标和，需要通过操作来增加和；反之，则无法调整，直接返回-1。操作次数可以通过计算差值的绝对值来确定。

C++：

// C++ 版本
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    ll res = 0;
    bool possible = true;
    int left = 0, right = n - 1;

    while (left < right) {
        if (a[left] != a[right]) {
            if (left + 1 == right) {
                possible = false;
                break;
            }
            ll diff = a[left] - a[right];
            if (diff > 0) {
                // 增加 left+1 处
                a[left + 1] += diff;
                res += diff;
            } else {
                // diff < 0, 增加 right-1 处
                a[right - 1] += -diff;
                res += -diff;
            }
            // 使两端相等
            a[left] = a[right];
        }
        left++;
        right--;
    }

    if (possible) {
        cout << res << "\n";
    } else {
        cout << -1 << "\n";
    }
    return 0;
}

Java：

// Java 版本
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        long res = 0;
        boolean possible = true;
        int left = 0, right = n - 1;

        while (left < right) {
            if (a[left] != a[right]) {
                if (left + 1 == right) {
                    possible = false;
                    break;
                }
                long diff = a[left] - a[right];
                if (diff > 0) {
                    // 增加 left+1 处
                    a[left + 1] += diff;
                    res += diff;
                } else {
                    // diff < 0, 增加 right-1 处
                    a[right - 1] += -diff;
                    res += -diff;
                }
                // 使两端相等
                a[left] = a[right];
            }
            left++;
            right--;
        }

        System.out.println(possible ? res : -1);
    }
}

Python：

n = int(input())
a = list(map(int, input().split()))
res = 0
possible = True

left = 0
right = n - 1

while left < right:
    if a[left] != a[right]:
        if left + 1 == right:
            possible = False
            break
        diff = a[left] - a[right]
        if diff > 0:
            a[left + 1] += diff
            res += diff
        else:
            a[right - 1] += -diff
            res += -diff
        a[left] = a[right]
    left += 1
    right -= 1

if possible:
    print(res)
else:
    print(-1)