Задача на массивы c++

Я понял как делать. Я просто не правильно прочитал условие сначала(думал, что можно прибавлять и вычитать в независимости от знака числа)

А так(кому интересно): Просто надо идти с конца, то есть из числа делать 0(если число четное, то делить на 2, а иначе прибавлять/вычитать 1. Для упрощения можно брать модуль числа, тк это не повлияет). И по пути считать кол-во операций, но при этом нужно учесть, что деление(умножение) выполняется для всех элементов, то есть кол-во операций = кол-во вычитаний + макс. кол-во делений на 2(среди всех элементов)

Ну, раз не надо скидывать решение, попробую описать словами.

В первом примере, к сожалению придётся до 16 прибавлять 16 раз. Ведь удвоение, как я понял, только на весь массив распространяется, а там есть -1.

Во втором, очевидно, одно сложение и три удвоения решают.

Что касается {6}, то это отличный пример для изучения.

Для умножения на константы как раз оптимизаторы компиляторов используют подобные алгоритмы.

Обычно идти надо сверху. Вначале выбрать ближайшее чётное, сделать вычитание, потом поделить на 2 сколько получится раз, потом всё сначала и так до 1. В обратном порядке получим самый быстрый алгоритм умножения на эту константу. При условии, что подряд идущие n умножений на 2 сводятся к битовому сдвигу влево на n.

В вашем случае, где доступно только увеличение (отрицательные рассматривать не будем, ведь по модулю там то же самое).

• 6-четное делим на 2, а последнее действие будет умножение: x*2
• 3-нечет, вычитаем 1. предпоследнее действие сложение: x+1; x*2
• 2-чет, действия: x2;x+1;x2
• 1-нечет: x+1;x2;x+1;x2
• 0-стоп. Для числа 6 алгоритм построен.

Так как в нашем распоряжении только два действия, то если обозначить сложение, как 0, а умножение как 1, то цепочку действий можно сохранить как [0,1,0,1]

Можно проделать такой анализ для всех элементов, а потом в цикле двигаться по этим командам для всех элементов массива, периодически удваивая его, если все команды это позволяют.

Возможно, это не самое лучшее решение.

Попробуем иначе.

Пусть наши числа - arr[N], счетчик операций как c, флаг продолжения f

int arr[N]; //Наш массив
bool f=1;
int c=0;
while(f){
  f=0;
  for(i=0;i<n;i++){
    if(!arr[i]%2){ //Нечётное
      if(arr[i]>0)
        arr[i]--;
      else
        arr[i]++;
      c++;
    }
    if(arr[i]) //Больше нуля - будем продолжать итерации
      f=1; //Show must go on
  }
  if(f){
    divide_arr(arr); //Деление массива на 2
    c++;
  }
}

printf("Количество операций: %d", c);

Код не проверял, не пинайте, если с ошибками. Это просто алгоритм.

Разберёмся с количеством операций для одного положительного числа. Минимальное количество операций равно
<число единиц в двоичной записи числа> + <число цифр в двоичной записи числа> - 1

Чтобы построить число n за это число операций, выпишем его двоичное представление без старшей цифры, которая всегда – единица. Положим k = 1 и будем перебирать биты n:

• в любом случае умножаем k на два;
• если соответствующий бит равен единице, то увеличиваем k на единицу.

Можно показать, что в конце k окажется равно n и что мы сделали соответствующее число операций.

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

Аналогично строится отрицательное число. Как строить ноль тоже понятно.

Если у нас не одно число а несколько, то число операций по ним есть
<число единиц в двоичных записях всех чисел> + <максимальное количество цифр в двоичной записи чисел> - 1

Потому что алгоритмы построения чисел можно так подравнять чтобы операции удвоения помогали всем построениям. Если для какого-то числа удвоений слишком много, то лишние удвоения делаются пока число нулевое.

#include <algorithm>
#include <iostream>

int main() {
    int n;
    std::cin >> n;
    int max_size = 1;
    int n_units = 0;
    for (int i = 0; i < n; ++i) {
        int ai;
        std::cin >> ai;
        int size = 0;
        for (; ai != 0; ai /= 2) {
            if (ai % 2 != 0) {
                ++n_units;
            }
            ++size;
        }
        max_size = std::max(max_size, size);
    }
    std::cout << (n_units + max_size - 1) << '\n';
}