gratiani
Авг. 20, 2016 10:09:20
Решаю задачу
http://codeforces.com/problemset/problem/144/A и не могу разобрать код с его решением.
in0 = int(input())
lst0 = [int(x) for x in input().split()]
minn = 1000
mini = 1000
maxn = 0
maxi = 0
for i in range(in0):
if lst0[i] <= minn:
minn = lst0[i]
mini = i
if lst0[i] > maxn:
maxn = lst0[i]
maxi = i
in1 = maxi + in0 - 1 - mini
if maxi > mini:
in1 -= 1
print(in1)
Может кто пояснить эти строки кода.
in1 = maxi + in0 - 1 - mini
if maxi > mini:
in1 -= 1
scidam
Авг. 22, 2016 02:39:43
В цикле программа находит максимальный и минимальный индексы ростов солдат, теперь, нам нужно их переставлять (менять местами рядом стоящих), пока в начале не будет с максимальным ростом, а в конце с минимальным.
По взаимному расположениею maxi (индекс максимального ростом) и mini (индекс минимального роста) существует только два варианта: maxi>mini и maxi<mini; рассмотрим каждый из этих вариантов:
1) mini>maxi: ind1, ind2, ….., maxii, indxx, indxx, minii, …. in0; В этом случае для того, чтобы догнать maxi в начало потребуется maxi-1 перестановок, а чтобы mini загнать в конец: in0-mini. Откуда имеем, что общее число в этом случае: maxi-1+in0-mini - это ваше число.
2) maxi>mini : ind1, ind2, ….., mini, indxx, indxx, maxi, …. in0 (вот такой ряд) и теперь начинаем переставлять:
чтобы maxi был в начале нужно сделать (maxi - 1) перестановок, при этом позиция mini когда мы будем гнать maxi в начало, измениться на mini+1; Итак, мы отогнали maxi в начало за maxi-1 перестановок, а mini стал mini+1; теперь гоним (mini+1) в конец. Для этого нам потребуется in0-(mini+1) перестановок. Таким образом, в общем потребуется:
(maxi-1) + in0-(mini+1) или на 1 меньше, чем предыдущее число для случая mini>maxi; значит в условии if maxi>mini достаточно отнять 1 от предыдщего значения, чтобы получить правильный результат для случая maxi>mini