Сортировка турелей(олимпиадное программирование)

@Anioni13 · Регистрация: 03.11.2019

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

B. Сортировка турелей
Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
ГЛаДОС сортирует турели! Дело в том, что она решила проверить состояние всех турелей — накануне Уитли зачем-то перекрасил часть турелей в другой цвет (обычная турель белого цвета). Хорошо еще, что турель-солистка и турель-предсказательница не пострадали. А еще хорошо, что Уитли не стал перекрашивать турель "Царь зверей", а то все закончилось бы не очень хорошо.

Всего в Aperture Laboratories осталось N турелей, каждая из них характеризуется силой Ai.

Сначала ГЛаДОС выстраивает белые турели в порядке невозрастания силы, а справа от них — цветные турели в порядке невозрастания силы. Теперь ей интересно: какова максимальная разница между двумя соседними турелями?

Формат ввода
В первой строке на вход подается одно целое число N ≤ 105 — количество турелей. Далее в N строках характеризуются сами турели: вводится пара чисел di и 1 ≤ Ai ≤ 109, где di=0, если турель белая, и di=1, если цветная. Ai — это сила турели.

Формат вывода
Выведите одно целое число — ответ на задачу.

Пример
Ввод Вывод
6 22
0 120
1 130
1 142
1 115
0 145
0 134
22

Хелпуйте!!!(С++)

@nalbe666 · 09.11.2019, 14:56

C++

#include <iostream>
#include <algorithm>
 
int main()
{
    size_t len;
    std::cin >> len;
    uint32_t* arr = new uint32_t[len];
    auto it1 = arr;
    auto it2 = std::make_reverse_iterator(arr + len);
    char ch;
    for (size_t i(0); i < len; ++i) {
        std::cin >> ch;
        std::cin >> (ch == '0' ? *it1++ : *it2++);
    }
 
    std::sort(std::make_reverse_iterator(it1), std::make_reverse_iterator(arr));
    std::sort(std::make_reverse_iterator(arr + len), it2);
 
    uint32_t maxDiff(0);
    for (it1 = arr; it1 < arr + len - 1; ++it1) {
        uint32_t diff = abs(int32_t(*it1) - int32_t(*(it1 + 1)));
        if (diff > maxDiff) maxDiff = diff;
    }
    std::cout << maxDiff;
 
    delete[] arr;
    return 0;
}

@Kuzia domovenok · 09.11.2019, 15:37

make_reverse_iterator

Напридумывали всякого

и не упомнишь!

@Anioni13 4 / 5 / 0 Регистрация: 03.11.2019 Сообщений: 16
		1
	Сортировка турелей(олимпиадное программирование) 09.11.2019, 11:04. Показов 2014. Ответов 2 Метки нет (Все метки) B. Сортировка турелей Ограничение времени 1 секунда Ограничение памяти 256Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt ГЛаДОС сортирует турели! Дело в том, что она решила проверить состояние всех турелей — накануне Уитли зачем-то перекрасил часть турелей в другой цвет (обычная турель белого цвета). Хорошо еще, что турель-солистка и турель-предсказательница не пострадали. А еще хорошо, что Уитли не стал перекрашивать турель "Царь зверей", а то все закончилось бы не очень хорошо. Всего в Aperture Laboratories осталось N турелей, каждая из них характеризуется силой Ai. Сначала ГЛаДОС выстраивает белые турели в порядке невозрастания силы, а справа от них — цветные турели в порядке невозрастания силы. Теперь ей интересно: какова максимальная разница между двумя соседними турелями? Формат ввода В первой строке на вход подается одно целое число N ≤ 105 — количество турелей. Далее в N строках характеризуются сами турели: вводится пара чисел di и 1 ≤ Ai ≤ 109, где di=0, если турель белая, и di=1, если цветная. Ai — это сила турели. Формат вывода Выведите одно целое число — ответ на задачу. Пример Ввод Вывод 6 22 0 120 1 130 1 142 1 115 0 145 0 134 22 Хелпуйте!!!(С++) 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	09.11.2019, 15:37	3
	make_reverse_iterator Напридумывали всякого и не упомнишь! 1

Сортировка турелей(олимпиадное программирование)

Решение