В каких ситуациях мой код не будет выводить правильный ответ?

@sphinX2502 · Регистрация: 05.10.2019

Студворк — интернет-сервис помощи студентам

Доброго времени суток. Интересует взлом кода вот этой задачи:
Вам задана последовательность целых чисел a1,a2,…,an.

Вы можете применять следующую операцию к этой последовательности: выбрать число x
и переместить все элементы равные x либо в начало, либо в конец массива a.
Обратите внимание, что за одну операцию вы перемещаете все элементы в одном направлении.

Например, если a=[2,1,3,1,1,3,2], вы можете получить следующие последовательности за одну операцию (для удобства, обозначим элементы равные x как x-элементы):

[1,1,1,2,3,3,2], если вы переместите все 1-элементы в начало;

[2,3,3,2,1,1,1], если вы переместите все 1-элементы в конец;

[2,2,1,3,1,1,3], если вы переместите все 2-элементы в начало;

[1,3,1,1,3,2,2], если вы переместите все 2-элементы в конец;

[3,3,2,1,1,1,2], если вы переместите все 3-элементы в начало;

[2,1,1,1,2,3,3], если вы переместите все 3-элементы в конец;

Вам нужно посчитать минимальное количество операций, после применения которых последовательность a
станет отсортирована в порядке неубывания.
Последовательность отсортирована в порядке неубывания, если для любого индекса i от 2 до n, выполняется условие ai−1≤ai.
Обратите внимание, что вам нужно ответить на q независимых запросов.

Входные данные

Первая строка содержит целое число q
(1≤q≤3*10^5) — количество запросов. Каждый запрос состоит из двух последовательных строк.

Первая строка каждого запроса содержит целое число n
(1≤n≤3⋅10^5) — количество элементов массива.

Вторая строка каждого запроса содержит n
целых чисел a1,a2,…,an (1≤ai≤n) — элементы массива.

Гарантируется, что сумма n
по всем запросам не превосходит 3⋅10^5.

Выходные данные
На каждый запрос выведите одно число — минимальное количество операций для сортировки последовательности a
в порядке неубывания.

Пример
Входные данные
3
7
3 1 6 6 3 1 1
8
1 1 4 4 4 7 8 8
7
4 2 5 2 6 2 7

Выходные данные
2
0
1

Я написал не очень эффективный код, который работает для большинства примеров:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
q = int(input())
 
def join__(m):
    return m[0] + m[1]
 
for i in range(q):
    n = int(input())
    m = [[], [int(i) for i in input().split()]]
    s = sorted(list(set(m[1])))
    print(s)
    flag = 0
    cnt = 0
    if sorted(join__(m)) == join__(m):
        print(0)
    else:
        while sorted(join__(m)) != join__(m):
            if flag >= len(s):
                break
            minim = s[flag]
            for i in range(m[1].count(minim)):
                m[0].append(minim)
            while minim in m[1]:
                m[1].remove(minim)
            # print(m[0], m[1])
            flag += 1
            cnt += 1
        print(cnt)

Мне кажется, что при некоторых входах, выгоднее будет двигать элементы вправо. Не могли бы вы подсказать, при каких входных данных так делать выгоднее в плане количества перестановок? Заранее спасибо.

@Fudthhh · 07.10.2019, 09:03

Сообщение от sphinX2502

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

Например: [6, 1, 3, 3, 6, 6]

@dondublon · 07.10.2019, 11:33

sphinX2502, это задача на динамическое программирование (если эта инфа поможет).

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@dondublon 4651 / 2071 / 366 Регистрация: 17.03.2012 Сообщений: 10,181 Записей в блоге: 6
	07.10.2019, 11:33
	sphinX2502, это задача на динамическое программирование (если эта инфа поможет). 0