笔试时间：2023年9月19日 秋招

第一题

题目：最优化存储 (四)

支付宝服务亿级消费者，每个支付宝的用户有自己独特的信息，假设每个会员存储的成本为ai；现在有n个会员，和一块存储容器m，希望用该容器存储更多的会员信息；存储优化是个相当复杂的过程，为了简化问题，存储规则如下：每个会员的存储成本可以用长度ai的线段表示。存储容器一块，可以用一段线段m表示。存储容器有个特性，如果会员i储在容器中间位置，存储成本为ai本身，但是线段容器两端有存储压缩技术，存储在靠两端位置的会员存储成本可以压缩到一半，即 ai/2，而且每个会员只能压缩一次。现在n个会员，每个会员存储成本为ai，以及有一块存储资源，希望你做存储优化，使用尽可能小的存储容器存储下所有会员的信息。

输入描述

第一行输入一个正整数n，代表会员的数量。

第二行输入n个正整数ai，代表每个会员信息的大小

1 <= n <= 10^5

2 <= ai <= 10^9

保证ai是偶数。

输出描述

一个正整数，代表使用的存储容器大小的最小值。

样例输入

5

2 4 4 8 2

样例输出

14

提示

将第三个、第四个会员放在两端即可。使用一个大小为14的容器即可存储全部会员信息。

参考题解

贪心，将最大的放在两端，其余的放在中间。

C++：[此代码未进行大量数据的测试，仅供参考]

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

typedef long long LL;

const int MAX_ELEMENTS = 100004;

int numbers[MAX_ELEMENTS];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    sort(numbers, numbers + n);

    LL ans = numbers[n - 2] / 2 + numbers[n - 1] / 2;  
    for (int i = 0; i < n - 2; i++) {
        ans += numbers[i];
    }

    cout << ans << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        int n = sc.nextInt();
        int[] numbers = new int[n];

        for (int i = 0; i < n; i++) {
            numbers[i] = sc.nextInt();
        }

        Arrays.sort(numbers);

        long ans = numbers[n - 2] / 2 + numbers[n - 1] / 2;
        for (int i = 0; i < n - 2; i++) {
            ans += numbers[i];
        }

        System.out.println(ans);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
numbers = list(map(int, input().split()))
numbers.sort()

ans = numbers[-2] // 2 + numbers[-1] // 2
for i in range(n - 2):
    ans += numbers[i]

print(ans)

第二题

题目：小红合并数组

小红有一个长度为n的数组，每次操作她可以选择一个i，将ai加到ai-1或者ai+1(如果i-1 或者i+1在下标范围内)，请问最少需要多少次操作，可以使数组的所有元素相等。

输入描述

一行一个整数n，表示数组的长度。

接下来一行n个整数a1,a2,...,an表示数组的初始值。

1 <= n <= 10^3

0 <= ai <= 10^4

输出描述

输出一个整数，表示最少的操作次数。

样例输入

5

1 4 2 3 5

样例输出

2

提示

第一次操作，将a2加到a1，数组变为[5,2,3,5]。

第二次操作，将a2加到a3，数组变为[5,5,5]。

参考题解

看成是对前缀和数组进行删除操作。因此枚举元素和的因子d，观察d，2d，3d……这个序列是不是原来的子序列即可，然后找到一个最长的子序列。

C++：[此代码未进行大量数据的测试，仅供参考]

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

typedef long long LL;

const int N = 1004;
int numbers[N], prefixSum[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> numbers[i];
        prefixSum[i] = prefixSum[i - 1] + numbers[i];
    }

    int totalSum = prefixSum[n];
    vector<int> divisors;

    for (int i = n; i >= 1; i--) {
        if (totalSum % i == 0) {
            divisors.push_back(i);
        }
    }

    int answer = 0;

    for (int d : divisors) {
        int w = totalSum / d;
        int c = 1;

        for (int i = 1; i <= n; i++) {
            if (prefixSum[i] == c * w) {
                c++;
            }
        }

        if (c > d) {
            answer = n - d;
            break;
        }
    }

    cout << answer << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = scanner.nextInt();
        }

        long[] prefixSum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + numbers[i - 1];
        }

        long totalSum = prefixSum[n];
        ArrayList<Integer> divisors = new ArrayList<>();

        for (int i = n; i > 0; i--) {
            if (t