logoChat01.ai

"Решите 2 задачи на одном из языков программирован...

创建于：2026年8月13日

使用 GPT-5.6 Thinking 回答 Chat01

问题

"Решите 2 задачи на одном из языков программирования (Python, Groovy, Java, JS, C++, C#), оцените их временную сложность O(n) и опишите работу алгоритма.

*///
*
Дан массив целых чисел длины N и целое число K. Разрешена операция удаления первого элемента массива с записью в его конец K-го элемента. Какое минимальное число шагов потребуется для того, чтобы сделать все элементы массива одинаковыми? -1, если это невозможно." - первая задача уже решена - тебе нужно решить только вторую написанную здесь задачу под второй звёздочкой

思考

Deriving the condition

I’m recognizing that every appended value comes from the fixed suffix beginning at position K. Therefore, that suffix must already be constant; otherwise mixed values keep reappearing. If it is constant, I only need to remove the latest differing prefix element.

Derived the condition

Worked for 35s

回答

Для второй задачи достаточно решения за O(N).

Идея

Пусть массив:

text
a1, a2, ..., aK, ..., aN

Одна операция превращает его в:

text
a2, a3, ..., aN, aK

При следующих операциях в конец будут последовательно добавляться:

text
aK, aK+1, ..., aN, aK, aK+1, ..., aN, ...

То есть элементы от K до N начинают циклически повторяться.

Отсюда следует важное условие: чтобы когда-нибудь весь массив стал одинаковым, все элементы

text
aK, aK+1, ..., aN

уже должны быть одинаковыми.

Если среди них есть разные значения — ответ -1.

Если же все они равны некоторому x, то все новые элементы, добавляемые справа, тоже будут равны x. Остаётся удалить слева все элементы, отличающиеся от x.

Поэтому ответ — позиция последнего элемента до K, который отличается от x. Если таких элементов нет, массив уже состоит из одинаковых элементов и ответ 0.

Python

python
n, k = map(int, input().split())
a = list(map(int, input().split()))

# Значение, которым в итоге должен быть заполнен весь массив
x = a[k - 1]

# Элементы с K-го до N-го должны быть одинаковыми
for i in range(k - 1, n):
    if a[i] != x:
        print(-1)
        break
else:
    answer = 0

    # Ищем последний элемент перед K, который отличается от x
    for i in range(k - 1):
        if a[i] != x:
            answer = i + 1   # количество операций, чтобы удалить его

    print(answer)

Пример

Пусть:

text
N = 5, K = 3
a = [2, 1, 7, 7, 7]

Часть от K до N:

text
[7, 7, 7]

состоит из одинаковых элементов, поэтому решение существует.

Операции:

text
[2, 1, 7, 7, 7]
[1, 7, 7, 7, 7]
[7, 7, 7, 7, 7]

Ответ:

text
2

Последний элемент, отличный от 7, находился на позиции 2, поэтому потребовалось две операции.

Временная сложность: O(N), поскольку массив просматривается не более двух раз.

Дополнительная память: O(1) помимо самого входного массива.

分享这个问答