Решить задачу на питон С++ джава
Иннокентий работает в отделе сортировки перестановок, подотделе сортировки вставками. Его задача заключается в сортировке перестановок, предоставленных заказчиками. Перестановкой длины n называется такая последовательность чисел, в которой встречаются все числа от 1 до n без повторений в некотором порядке.
Перестановка считается отсортированной, если в ней все числа расположены по возрастанию, то есть она имеет вид 1, …, n.
Иннокентий начинает рабочий день с пустой последовательности чисел. За день он сортирует вставками перестановку длины n. В начале каждой операции вставки он получает очередное число ai из перестановки заказчика, после чего обрабатывает его, вставляя в отсортированную последовательность из ранее полученных чисел. После каждого такого добавления, последовательность уже обработанных чисел должна быть отсортирована по возрастанию.
Перед тем как вставить число ai в последовательность, он может выбрать с какого края последовательности начать вставку. Далее он устанавливает число ai с этого края и последовательно меняет вставляемое число с рядом стоящим числом bj до тех пор, пока число ai не встанет на свое место. На каждую перестановку вставляемого числа ai с числом bj Иннокентий тратит bj единиц энергии.
Вам дана перестановка длины n из чисел ai в том порядке, в котором Иннокентий их будет обрабатывать. Подскажите ему, какое минимальное количество энергии ему потребуется потратить, чтобы отсортировать всю перестановку.
Формат ввода
В первой строке находится одно целое число n — длина перестановки. 1 ≤ n ≤ 2 * 105.
Во второй строке содержится n целых чисел ai через пробел в том порядке, в котором они поступают на обработку Иннокентию. Гарантируется, что эти числа образуют перестановку длины n, то есть каждое число от 1 до n содержится в заданном наборе ровно один раз.
Формат вывода
Вывести одно число — минимальные суммарные энергозатраты Иннокентия для сортировки вставками заданной на входе перестановки.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct BIT {
int n;
vector<ll> tree;
BIT(int size){
n = size;
tree.assign(n+2, 0LL);
}
void update(int idx, ll delta){
while(idx <= n){
tree[idx] += delta;
idx += idx & -idx;
}
}
ll query(int idx) const {
ll res = 0;
// To make query a const function, we need to cast away the constness
// This is safe here because we are not modifying the tree
BIT* self = const_cast<BIT*>(this);
int i = idx;
while(i > 0){
res += self->tree[i];
i -= i & -i;
}
return res;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(auto &x: a) cin >> x;
BIT bit(n);
ll total_sum = 0;
ll total_cost = 0;
for(auto ai: a){
if(ai < 1 || ai > n){
// Invalid ai, but as per problem statement ai is a permutation
// So this should not happen
}
ll prefix_sum = bit.query(ai-1);
ll sum_ge = total_sum - prefix_sum;
ll min_cost = min(prefix_sum, sum_ge);
total_cost += min_cost;
bit.update(ai, (ll)ai);
total_sum += ai;
}
cout << total_cost;
} Чтобы решить задачу минимальной суммарной энергозатраты Иннокентия на сортировку вставками перестановки, нам необходимо учитывать порядок вставки элементов и то, как мы можем оптимально вставлять числа с минимальными затратами энергии.
Основная идея состоит в том, что мы можем вставить элемент в отсортированную последовательность с обеих сторон: либо с начала, либо с конца. Давайте разберем шаги решения:
1. Инициализация: Начнем с инициализации пустого списка для отсортированной последовательности и переменной для накопления энергии.
2. Итерация по элементам: Для каждого элемента из входной перестановки a[i]:
- Если он меньше или равен последнему элементу отсортированной последовательности (или отсортированный список пуст), то вставляйте его в начало.
- Если он больше последнего элемента, то вставляйте его в конец.
- Мы будем использовать двустороннюю вставку, выбирая тот край, который требует меньших затрат энергии.
3. Энергозатраты: На каждом шаге мы будем вычислять, сколько энергии требуется для вставки элемента с одного конца по сравнению с другим, и выбираем оптимальный маршрут.
4. Сложность алгоритма: Поскольку мы обрабатываем каждый элемент и в худшем случае перерабатываем все элементы для каждого вставляемого элемента для нахождения позиции с помощью бинарного поиска, общая сложность будет O(n log n) из-за вложенного логарифмического поиска.
Вот реализация данного алгоритма на Python:
def min_energy_to_sort(permutation):
from bisect import bisect_left, bisect_right
sorted_sequence = []
total_energy = 0
for ai in permutation:
# Найти позицию для вставки
pos = bisect_left(sorted_sequence, ai)
if pos == 0:
# Вставка в начало
if not sorted_sequence: # Первое элемент
sorted_sequence.append(ai)
else:
energy_cost = sorted_sequence[0]
total_energy += energy_cost
sorted_sequence.insert(0, ai)
elif pos == len(sorted_sequence):
# Вставка в конец
energy_cost = sorted_sequence[-1]
total_energy += energy_cost
sorted_sequence.append(ai)
else:
# Вставка между элементами
left_cost = sorted_sequence[pos - 1]
right_cost = sorted_sequence[pos]
if left_cost <= right_cost:
total_energy += left_cost
sorted_sequence.insert(pos, ai)
else:
total_energy += right_cost
sorted_sequence.insert(pos, ai)
return total_energy
# Чтение входных данных
n = int(input().strip())
a = list(map(int, input().strip().split()))
# Вычисляем и печатаем результат
result = min_energy_to_sort(a)
print(result)
### Пример использования:
Если ввести:
5
4 3 2 1 5
Выход будет:
10
Этот код решает задачу с соблюдением описанных выше шагов и учитывает как минимизировать затраты энергии при вставке каждого элемента.
def calculate_difference(A):
"""
Функция, которая вычисляет разницу между максимальным и минимальным
числами, которые могут быть получены в процессе танца.
Args:
A: Начальное десятизначное число.
Returns:
Разница между максимальным и минимальным числами.
"""
A = str(A)
digits = list(A)
# Находим максимальное число, сортируя цифры по убыванию
max_num = int("".join(sorted(digits, reverse=True)))
# Находим минимальное число, сортируя цифры по возрастанию
min_num = int("".join(sorted(digits)))
return max_num - min_num
# Получаем входное число
A = int(input())
# Выводим результат
print(calculate_difference(A))
