2 thoughts on “e-olymp 8963. Наименьшие влево”

1. • Нужно сделать правильные отступы.
   • Вместо ссылки на ideone стоит ссылка на текущую страницу.
   • Когда в пояснении Вы пишите про min, Вы ведь имеете в виду переменную из кода? Тогда почему размечаете её как математическую формулу?
   • Ну и самое главное — алгоритм плохой. Он правильный. И задачу решает. Но плохой. Вложенные циклы в нем выполняют слишком много операций. Вы просматриваете массив и опускаете каждый минимальный элемент на одну позицию вниз. Хотя заранее знаете где должны оказаться все минимальные элементы. Даже если на вход программы дать массив в котором минимальный элемент один и он уже стоит слева, программа будет $n$ раз просматривать $n$ элементов, сравнивая их с минимальным. Другими словами, Ваш алгоритм выполняет порядка $O\left(n^2\right)$ операций. А нужно $O\left(n\right)$. Конечно, при таких маленьких массивах мы эффекта не увидим, но для больших данных разница будет огромной.

   Войдите, чтобы ответить

2. Да. Такой вариант мне больше нравится. Если еще и размер (capacity) поставить сразу по числу элементов, то решение будет иметь линейную сложность. Хотя, все это «из пушки по воробьям» — два вектора вместо одного массива.
   Задача легко решается без всяких трюков и сложных структур данных:

   C++

   #include <iostream> int main() { int n; std::cin >> n; int arr[n]; std::cin >> arr[0]; int min = arr[0]; for(int i = 1; i < n; i++) { std::cin >> arr[i]; min = std::min(min, arr[i]); } int j = n-1; for(int i = n-1; i >= 0; i--) if (arr[i] != min) arr[j--] = arr[i]; while (j >= 0) arr[j--] = min; for(int i = 0; i < n; i++) std::cout << arr[i] << " "; }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   #include <iostream> int main() {     int n; std::cin >> n;     int arr[n]; std::cin >> arr[0];     int min = arr[0];     for(int i = 1; i < n; i++) {         std::cin >> arr[i];         min = std::min(min, arr[i]);     }     int j = n-1;     for(int i = n-1; i >= 0; i--)         if (arr[i] != min) arr[j--] = arr[i];     while (j >= 0) arr[j--] = min;     for(int i = 0; i < n; i++) std::cout << arr[i] << " "; }

   В строках 10-12 все минимальные элементы стираются, а в 13-й они добисываются на нужные места в начало.
   Но зачтено и в Вашей версии. С учетом того, что прошлая Ваша попытка фактически реализовала сортировку пузырьком в самой не эффективной версии, даю Вам задачу 2663, которая поможет разобраться с этим алгоритмом. Желаю успехов.

   Войдите, чтобы ответить