Алгоритм медленных сумм

Question

Предположим, у нас есть список из N чисел, и мы повторяем следующую операцию, пока у нас не останется только одно число: выберите любые два последовательных числа и замените их их суммой. Более того, мы связываем штраф с каждой операцией, равный значению нового числа, и называем штраф для всего списка как сумму штрафов за каждую операцию.

Примечание: последовательные числа означают, что их индексы в массив последовательные, а не то, что их значения последовательные. Например, учитывая список [1, 2, 3, 4, 5], мы могли бы выбрать 2 и 3 для первой операции, которая преобразует список в [1, 5, 4, 5] и повлечет штраф в размере 5 . Цель этой задачи - найти наихудший возможный штраф для данного ввода.

Ограничения: 1 ≤ N ≤ 10 ^ 6 1 ≤ Ai ≤ 10 ^ 7, где * Ai обозначает i-й начальный элемент массив. Сумма значений N по всем тестам не будет превышать 5 * 10 ^ 6.

Example
arr = [4, 2, 1, 3]
output = 23
First, add 4 + 2 for a penalty of 6. Now the array is [6, 1, 3]
Add 6 + 1 for a penalty of 7. Now the array is [7, 3]
Add 7 + 3 for a penalty of 10. The penalties sum to 23.

int getTotalTime(int[] arr) {}

Answer 1

Это жадная проблема. Смысл в том, чтобы заметить, что мы всегда должны следить за максимально возможной суммой на каждой итерации. В вашем случае [4, 2, 1, 3] первая самая большая сумма - 6, затем 7, а затем 10.

Проблема возникает, когда самая большая сумма появляется несколько раз, например [5, 3, 7, 1], затем вам нужно выбрать, что лучше начать с [5, 3] или [7, 1].

#include <bits/stdc++.h>
using namespace std;

int n = 6;                       //array size
int a[] = {2, 1, 7, 1, 5, 3};    //array

vector<pair<int, int>> v;        //positions we will analyse

void analyse(){                  //this method gets the positions with biggest sum
    int sum = 0;
    for(int i = 1; i < n; i++) sum = max(sum, a[i - 1] + a[i]);
    for(int i = 1; i < n; i++) if(a[i - 1] + a[i] == sum) v.push_back(make_pair(i - 1, i));
}

int evaluate_penalty(int i, int j){   //given a position, this method finds
    int l = i, r = j;                 //the biggest penalty starting there
    int penalty = a[i] + a[j];
    int val = penalty;
    while(i != 0 || j != n - 1){
        if(l > 0 && r < n - 1) {
            if(a[l - 1] > a[r + 1]) l--;
            else r++;
        }
        else if(l > 0) l--;
        else r++;

        val += (l != i ? a[l] : 0) + (r != j ? a[r] : 0);
        penalty += val;
        i = l; j = r;
    }
    return penalty;
}

int max_penalty(){            //this method finds the biggest penalty
    v.clear();                //within all the possible starting positions.
    analyse();
    int maxPenalty = 0;
    for(int i = 0; i < v.size(); i++){
        maxPenalty = max(maxPenalty, evaluate_penalty(v[i].first, v[i].second));
    }
    return maxPenalty;
}

int main(){
    cout<<max_penalty()<<endl;
    return 0;
}

Сложность O (n²) , НО в большинстве случаев это будет быть О (п) . Учитывая, что наибольшая сумма между двумя последовательными числами равна s , сложность зависит от того, сколько пар последовательных чисел суммируют s . Если есть только один (как в вашем примере [4, 2, 1, 3], он завершит sh за одну итерацию, следовательно, O (n). Если массив имеет что-то вроде [1, 1, 1, 1, 1, ..., 1], он займет O (n²).

Answer 2

Вот оптимизированное решение в Javascript, включающее пару тестовых примеров. Ключевой принцип заключается в том, что наивысший штраф может быть получен на каждом этапе путем добавления двух самых больших элементов в массив.

//Begin Solution
function getTotalTime(arr) {
    function getTotal(a){
      if(a.length==2)
        return a[0]+a[1]
      else{
        const penalty = a[a.length-1]+a[a.length-2]
        return penalty+getTotal([...a.slice(0,a.length-2),penalty])
      }
          
    }
  return getTotal(arr.slice(0,arr.length).sort((a,b)=>a-b))
}
 //End Solution

  // These are the tests we use to determine if the solution is correct.

  function printInteger(n) {
    var out = '[' + n + ']';
    return out;
  }
  
  var test_case_number = 1;
  
  function check(expected, output) {
    var result = (expected == output);
    var rightTick = "\u2713";
    var wrongTick = "\u2717";
    if (result) {
      var out = rightTick + ' Test #' + test_case_number;
      console.log(out);
    }
    else {
      var out = '';
      out += wrongTick + ' Test #' + test_case_number + ': Expected ';
      out += printInteger(expected);
      out += ' Your output: ';
      out += printInteger(output);
      console.log(out);
    }
    test_case_number++;
  }
  
  var arr_1 = [4, 2, 1, 3];
  var expected_1 = 26;
  var output_1 = getTotalTime(arr_1);
  check(expected_1, output_1);
  
  var arr_2 = [2, 3, 9, 8, 4];
  var expected_2 = 88;
  var output_2 = getTotalTime(arr_2);
  check(expected_2, output_2);

  

Answer 3

Я решил вот так, но не уверен, оптимально это или нет

static int getTotalTime(int[] arr) {
        List<Integer> output = new ArrayList<>();
        Arrays.stream(arr).forEach(output::add);
        if (output.size() < 3) {
            return output.stream().reduce((a, b) -> a + b).get();
        }

        int sum = 0;
        List<Integer> max1 = new ArrayList<>();
        max1.add(0);
        for (int i = 2; i < output.size(); i++) {
            if (output.get(i) + output.get(i - 1) > output.get(max1.get(0)) + output.get(max1.get(0) + 1)) {
                max1 = new ArrayList<>();
                max1.add(i - 1);
            }else if (output.get(i) + output.get(i - 1) == output.get(max1.get(0)) + output.get(max1.get(0) + 1)) {
                max1.add(i - 1);
            }
        }

        sum = sum + output.get(max1.get(0)) + output.get(max1.get(0) + 1);

        List newList = new ArrayList(output);
        newList.set(max1.get(0), output.get(max1.get(0)) + output.get(max1.get(0) + 1));
        newList.remove(max1.get(0) + 1);

        int remainingSum = getTotalTime(newList);

        for (int i = 1; i < max1.size(); i++) {
            newList = new ArrayList(output);
            newList.set(max1.get(i), output.get(max1.get(i)) + output.get(max1.get(i) + 1));
            newList.remove(max1.get(i) + 1);
            int nextRemainingSum = getTotalTime(newList);
            if (nextRemainingSum > remainingSum) {
                remainingSum = nextRemainingSum;
            }
        }

        sum += remainingSum;

        return sum;
    }

    static int getTotalTime(List<Integer> output) {
        int sum = 0;
        while (output.size() > 2) {
            int max1 = 0;
            for (int i = 2; i < output.size(); i++) {
                if (output.get(i) + output.get(i - 1) > output.get(max1) + output.get(max1 + 1)) {
                    max1 = i - 1;
                }
            }
            sum += output.get(max1) + output.get(max1 + 1);
            output.set(max1, output.get(max1) + output.get(max1 + 1));
            output.remove(max1 + 1);
        }

        return sum + output.stream().reduce((a, b) -> a + b).get();

    }