Я пытаюсь найти алгоритм O (n) для этой проблемы, но не могу сделать это, даже потратив 3-4 часа. Тайм-аут методом грубой силы (O (n^2)). Я не совсем понимаю, как это сделать? Требуется ли решение для динамического программирования?
http://acm.timus.ru/problem.aspx?space=1&num=1794
Короче проблема в следующем:
Некоторые ученики сидят в кругу, и у каждого из них есть свой выбор относительно того, когда ему нужно задать вопрос учителю. Учитель будет задавать вопросы только по часовой стрелке. Например:
5
3 3 1 5 5
Это означает, что есть 5 студентов и:
1st student wants to go third
2nd student wants to go third
3rd student wants to go first
4th student wants to go fifth
5th student wants to go fifth.
Вопрос в том, где учитель должен начать задавать вопросы, чтобы максимальное количество учеников получило очередь, как они хотят. Для этого конкретного примера ответ 5, потому что
3 3 1 5 5
2 3 4 5 1
Вы можете видеть, что, начиная с пятого студента с 1-го, 2 студента (3 и 5) получают выбор, как они хотели. Для этого примера ответ 12-й студент:
12
5 1 2 3 6 3 8 4 10 3 12 7
потому что
5 1 2 3 6 3 8 4 10 3 12 7
2 3 4 5 6 7 8 9 10 11 12 1
четыре ученика выполнили свой выбор.