Решение задачи Наиболее нестабильный массив с Codeforces
С пояснением   Просмотров: 92
Вам даны два целых числа n и m. Вам нужно построить массив a длины n состоящий из неотрицательных целых чисел (т.е. целых чисел больших или равных нулю) такой, что сумма элементов этого массива в точности равна m и величина ∑i=1n−1|ai−ai+1| максимально возможная. Напомним, что |x| — абсолютное значение x.
Другими словами, вы хотите максимизировать сумму абсолютных разностей между соседними (последовательными) элементами. Например, если массив a=[1,3,2,5,5,0], то величина, описанная выше, для этого массива равна |1−3|+|3−2|+|2−5|+|5−5|+|5−0|=2+1+3+0+5=11. Заметьте, что этот пример не показывает оптимальный ответ, но показывает, как считается необходимое значение для какого-то массива.
Вам нужно ответить на t независимых наборов тестовых данных.
Другими словами, вы хотите максимизировать сумму абсолютных разностей между соседними (последовательными) элементами. Например, если массив a=[1,3,2,5,5,0], то величина, описанная выше, для этого массива равна |1−3|+|3−2|+|2−5|+|5−5|+|5−0|=2+1+3+0+5=11. Заметьте, что этот пример не показывает оптимальный ответ, но показывает, как считается необходимое значение для какого-то массива.
Вам нужно ответить на t независимых наборов тестовых данных.
Пояснение к задаче
Если n=1, то ответ равен 0. Иначе лучшим способом является построить массив [0,m,0,…,0]. Для n=2 мы не можем достичь ответа лучше, чем m, а для n>2 мы не можем достичь ответа лучше, чем 2m, потому что каждая единица не может быть использована больше, чем дважды. Таким образом, ответ можно представить как min(2,n−1)⋅m.