Решение задачи Наиболее нестабильный массив с Codeforces

С пояснением   Просмотров: 34

Вам даны два целых числа 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 независимых наборов тестовых данных.

Код 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        cout << min(2, n - 1) * m << endl;
    }
    return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Если n=1, то ответ равен 0. Иначе лучшим способом является построить массив [0,m,0,…,0]. Для n=2 мы не можем достичь ответа лучше, чем m, а для n>2 мы не можем достичь ответа лучше, чем 2m, потому что каждая единица не может быть использована больше, чем дважды. Таким образом, ответ можно представить как min(2,n−1)⋅m.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES bminhojkhon03@gmail.com Карта сайта