解题思路

这是一个贪心算法问题：

  1. 每次从数组的左端或右端取出一个数
  2. 第 次取出的数会乘以 作为得分
  3. 取数的规则：
    • 如果左端数小于右端数，取左端数
    • 如果左端数大于右端数，取右端数
    • 如果相等，继续比较下一对数

代码

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

bool compare(vector<int>& arr, int left, int right) {
    if (left >= right) return true;
    if (arr[left] > arr[right]) return false;
    if (arr[left] < arr[right]) return true;
    return compare(arr, left + 1, right - 1);
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    
    // 读入数组
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    // 计算得分
    int sum = 0;
    int left = 0, right = n - 1;
    for (int i = 0; i < n; i++) {
        if (compare(arr, left, right)) {
            sum += (i + 1) * arr[left++];
        } else {
            sum += (i + 1) * arr[right--];
        }
    }
    
    cout << sum << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    private static int[] arr;
    
    private static boolean compare(int left, int right) {
        if (left >= right) return true;
        if (arr[left] > arr[right]) return false;
        if (arr[left] < arr[right]) return true;
        return compare(left + 1, right - 1);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n];
        
        // 读入数组
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 计算得分
        int sum = 0;
        int left = 0, right = n - 1;
        for (int i = 0; i < n; i++) {
            if (compare(left, right)) {
                sum += (i + 1) * arr[left++];
            } else {
                sum += (i + 1) * arr[right--];
            }
        }
        
        System.out.println(sum);
        sc.close();
    }
}

def compare(arr, left, right):
    if left >= right:
        return True
    if arr[left] > arr[right]:
        return False
    if arr[left] < arr[right]:
        return True
    return compare(arr, left + 1, right - 1)

# 读入数据
n = int(input())
arr = list(map(int, input().split()))

# 计算得分
sum = 0
left, right = 0, n - 1
for i in range(n):
    if compare(arr, left, right):
        sum += (i + 1) * arr[left]
        left += 1
    else:
        sum += (i + 1) * arr[right]
        right -= 1

print(sum)

算法及复杂度

  • 算法：贪心算法
  • 时间复杂度：，其中 为数组长度。每次比较可能需要遍历到数组中间
  • 空间复杂度：，递归调用栈的深度