Решение задачи Задоминированный подмассив с Codeforces
Без пояснения   Просмотров: 118
Назовем массив t задоминированным значением v в следующем случае.
Во-первых, массив t должен состоять хотя бы из 2 элементов. Теперь, давайте посчитаем количество вхождений каждого числа num в t и назовем данное значение occ(num). Тогда, t — задоминирована (числом v) тогда (и только тогда), когда occ(v)>occ(v′) для любого другого числа v′. Например, массивы [1,2,3,4,5,2], [11,11] и [3,2,3,2,3] задоминированы (числами 2, 11 и 3 соответственно), но массивы [3], [1,2] и [3,3,2,2,1] — нет.
Небольшая заметка: так как любой массив может быть задоминирован только одним числом, то мы можем не уточнять данное число и просто говорить, что массив либо задоминирован, либо нет.
Вам задан массив a1,a2,…,an. Определите его самый короткий задоминированный подмассив, либо скажите, что таких нет.
Подмассив массива a — это последовательная часть массива a, другими словами массив ai,ai+1,…,aj для некоторых 1≤i≤j≤n.
Во-первых, массив t должен состоять хотя бы из 2 элементов. Теперь, давайте посчитаем количество вхождений каждого числа num в t и назовем данное значение occ(num). Тогда, t — задоминирована (числом v) тогда (и только тогда), когда occ(v)>occ(v′) для любого другого числа v′. Например, массивы [1,2,3,4,5,2], [11,11] и [3,2,3,2,3] задоминированы (числами 2, 11 и 3 соответственно), но массивы [3], [1,2] и [3,3,2,2,1] — нет.
Небольшая заметка: так как любой массив может быть задоминирован только одним числом, то мы можем не уточнять данное число и просто говорить, что массив либо задоминирован, либо нет.
Вам задан массив a1,a2,…,an. Определите его самый короткий задоминированный подмассив, либо скажите, что таких нет.
Подмассив массива a — это последовательная часть массива a, другими словами массив ai,ai+1,…,aj для некоторых 1≤i≤j≤n.