笔试时间：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] // 2for 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