Искам да пусна тази тема, защото се опитах да реша тази задача.Избрах не особено ефективен метод, и judge дава 30/100 въпреки, че кода работи коректно. Помогна ми MarinBG. Той каза, че тази задача е една от агоритмичните задачи в този курс.(Fundamentals C++), ако искате се опитайте и вие. А тя сега е подходяща, за да упражните асоциативните контейнери.
Задачата наистина е приятна, защото изисква намирането на по-оптимално решение.
Наивният подход е да пазим отсечките в един контейнер и за всяка точка да ги проверяваме всичките, докато не открием съвпадение или не стигнем последната. Това е валидно решение, но само за малък брой входни данни, тъй като броят операции, които се извършват клони към брой отсечки * брой точки.
В условието е казано:
There will be between 1 and 10000 ranges (inclusive).
There will be between 1 and 100000 check numbers (inclusive).
In 30% of the tests, there will be no more than 10 ranges and 10 numbers.
Или с други думи, при 7 от 10 теста може да се наложи да направим до 1 000 000 000 (10 000 * 100 000) итерации.
Наивното решение не се справя и се налага да се помисли за начин, при който проверките няма да нарастват толкова бързо спрямо количеството входни данни.
Няма какво да се направи по отношение на броя точки (ще трябва да проверим всяка една по отделно), така че остава да се помисли в посока намаляване на проверките за всяка точка в колекцията от отсечки. Има структури, при които елементите са сортирани и върху които може да се приложи двоично търсене, което е с логаритмична сложност (при 1000 елемента ще провери само до 10 от тях, при 10000 - до 14) и използването им в тази задача значително ще намали макс. брой итерации (до 14 * 100 000).
Това е популярна алгоритмична задача, макар че решението ѝ по-скоро се свежда до използването на подходяща структура за съхранение на данните, а не толкова до използването на специфичен алгоритъм.
Заради големият брой входно-изходни операции в тази задача, бих препоръчал да използвате и следните оптимизации (смъкват около 0.250 сек. от времето за изпълнение в Judge), но при оптимален алгоритъм, решението минава и без тях:
int main() {
std::ostream::sync_with_stdio(false);
std::istream::sync_with_stdio(false);
std::cin.tie(nullptr);
....
}
В линка по-горе има примерен алгоритъм за решаването на този проблем, а това е мое решение, но преди да ги погледнете, ще е добре сами да се поборите с проблема. :)
std::ostream::sync_with_stdio(false);
std::istream::sync_with_stdio(false);
std::cin.tie(nullptr);
Може, ли да обясните горната част от код?
input.clear(); защо тябва да "чистим" потока, това по-ефективно ли е? И как се разбира,кога да го използваме?
input.str(line); с това се взима едим ред, така ли? Имаше и .get(за char), kolioi го беше използвал в задачата decomprres.
Тук има добро обяснение на I/O оптимизациите. От извора: sync_with_stdio, tie
Синхронизацията може да се изключи и директно през базовия (ios_base) клас:
Извиквам clear() метода върху стрийма за да изчистя всякакви грешки (error bits), ако има такива, останали от предишното му използване. В случая го правя превантивно, защото искам да преизползвам стрийма, вместо да създавам нов на всяка итерация. Ако създаваш нов стрийм това не е необходимо.
str(text) "зарежда" стрийма с ново съдържание.
Предполагам, питаш за следните варианти:
Както съм писал в коментарите в кода, първият вариант е общ (може да работи с различни колекции) и заради това може да е по-бавен, вместо специализирания, който е дефиниран за конкретната колекция. Дори и в случай на малки разлики в бързодействието, вторият вариант е за предпочитане, защото не се налага импортването на външна библиотека.
Относно оптимизациите за вход/изход - да, задачата работи и без тях, но ако погледнеш времената в Judge, ще забележиш, че без тях решението минава за 0.350 - 0.400 сек. и за около 0.115 сек., ако ги има.