Найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям

@melomanmmmmmm · Регистрация: 17.10.2019

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

В парке города Питсбурга есть чудесная аллея, состоящая из N посаженных в один ряд деревьев, каждое одного из K сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из K видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.

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

В первой строке входного файла находятся два числа N и K ( 1 ≤ N , K ≤ 250000 ). Во второй строке входного файла следуют N чисел (разделенных пробелами), i -ое число второй строки задает цвет i -ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета

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

В выходной файл выведите два числа, координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите любой.

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

вот что я сделал:

C++

#include <iostream>
 
using namespace std;
 
int main(){
 
int n, a[n], max, u = 1, mu;
long k;
cin >> n >> k;
string s;
cin >> s;
 
for (int i; i < s; i++){
    if (strlen(i) < k){
        a = new string [i + amountAdd];
        if (strlen(a)>max){
            max=strlen(a);
            mu=u;
        }
    }
    else{
        a = new string [0 + amountRem];
        u = u + 1;
    }
cout >> max >> mu;
 
return 0;
}

помогите исправить.

Новичок · 18.10.2019, 05:02

Исправить? Тут все переписывать надо.

untyped · 18.10.2019, 05:31

GOOGLE, кагбэ намекает....

site:cyberforum.ru ( 1 ≤ N , K ≤ 250000 )

Новичок 1642 / 1091 / 487 Регистрация: 17.07.2012 Сообщений: 5,345
	18.10.2019, 05:02	2
	Исправить? Тут все переписывать надо. 0

untyped 530 / 180 / 38 Регистрация: 18.08.2012 Сообщений: 904
	18.10.2019, 05:31	3
	GOOGLE, кагбэ намекает.... site:cyberforum.ru ( 1 ≤ N , K ≤ 250000 ) 0

Опции темы