Как реализовать цикл for для данной задачи C#

Question

Разработчики нового парка развлечений хотят построить аттракцион американские горки. Они считают, что большее удовольствие на этом аттракционе люди получают при большем перепаде высот между соседними участками. Однако снабженцы уже закупили N опор, высоты которых известны. Помогите разработчикам парка расставить опоры в линию в таком порядке, чтобы сумма перепадов высот всех соседних опор была максимальной (перепадом высот называется модуль разности высот двух соседних опор).

Формат входных данных В первой строке одно целое число N, 2<= N <= 10^5, - число опор. В следующей строке N разделенных пробелами целых неотрицательных чисел, каждое не превышает 10^8 высоты закупленных опор.

Формат выходных данных В единственной строке целое неотрицательное число - максимально возможная сумма перепадов высот.

public static class CF10

{
    public static void Main()
    {
        int N = 5;
        int[] countHeight = new int[] { 10, 20, 30, 40, 50 };
        Array.Sort(countHeight);
        int[] result = new int[5];

        for (int i = 0; i < countHeight.Length/2; i++)
        {
            result = 
        }
    }    
}

Answer 1

Судя по подразумевающейся сложности (не хуже nlogn), нужен всё-таки жадный алгоритм.

Будем собирать цепочку, начав с минимального (или максимального, неважно) элемента, и пробовать притыкать к ней справа и слева минимальный и максимальный элемент из оставшихся, выбирая по наилучшей разнице с большим и маленьким концом цепочки (выбор из четырёх разностей).

Сравнение на случайных данных с полным перебором перестановок вроде проходит

print(maxdiffs([3, 6, 13, 2, 7, 18]))

>> 53   (6 13 2 18 3 7)

Код на Python:

import itertools, random

def md(a):
    best = 0
    for perm in itertools.permutations(a):
        sm = 0
        for i in range(1, len(perm)):
            sm += abs(perm[i] - perm[i-1])
        best = max(sm, best)
    return best



def maxdiffs(a):
    a.sort()
    res = 0
    head = tail = 0
    l = 1
    r = len(a) - 1
    while l <= r:
        dlh = abs(a[l] - a[head])
        dlt = abs(a[tail] - a[l])
        drh = abs(a[r] - a[head])
        drt = abs(a[tail] - a[r])
        mx = max(drh, drt, dlh, dlt)
        res += mx
        if mx == drh:
            head = r
            r -= 1
        elif mx == drt:
            tail = r
            r -= 1
        elif mx == dlh:
            head = l
            l += 1
        else:
            tail = l
            l += 1
    return res

a = [random.randrange(1, 100) for _ in range(8)]
print(a)
print(maxdiffs(a))
print(md(a))

БЛОГ НА HUSL

Как реализовать цикл for для данной задачи C#

Ответы (1 шт):