Решение задачи Входящие (100500) с Codeforces

С пояснением   Просмотров: 31


У Алексея в почтовом ящике накопилось много писем. Некоторые из них уже прочитаны, а некоторые — еще нет.

Почтовая программа Алексея может либо показывать список всех писем, либо отображать содержимое какого-то одного письма. Как только программа отображает содержимое непрочитанного письма, оно становится прочитанным (если программа отображает содержимое уже прочитанного письма, ничего не происходит). За одно нажатие мышки можно выполнить любую из следующих операций:

Перейти из списка писем к содержимому любого письма.
Вернуться к списку писем из режима отображения письма.
В режиме отображения письма перейти к следующему либо предыдущему письму в списке. Нельзя пытаться перейти к предыдущему письму, если текущее письмо первое в списке, или перейти к следующему письму, если текущее письмо последнее в списке.
Удалять письма из списка или менять их местами программа не может.

Алексей хочет как можно быстрее прочитать все еще непрочитанные письма и пойти смотреть футбол. Сейчас он находится в списке всех писем и видит, какие письма прочитаны, а какие — нет. Какое минимальное количество операций Алексею придется совершить, чтобы все письма в ящике стали прочитанными?

Код

#include <bits/stdc++.h>
using namespace std;
int x,p,a;
main(){
    cin >> x;
    while(cin >> x)
        a += (2 - p) * x, p = x;
    cout << max(a - 1, 0);
}

         

Администратор Photo Автор: Администратор


Наилучшая стратегия такова: для каждого непрерывного отрезка из непрочитанных писем откроем первое письмо, пролистаем до последнего в том же отрезке, если есть еще непрочитанные письма, вернемся к списку.

Легко показать, что лучше мы сделать не сможем: для выбранного отрезка посмотрим на момент, когда мы прочитаем последнее письмо из него. Если мы еще не все прочитали, нам придется либо вернуться в список, либо переместиться в одно из соседних писем, среди которых нет непрочитанных. Таким образом, Для каждого отрезка, кроме одного, мы должны совершить лишнее действие, которое не приводит к прочтению нового письма. Эта же оценка достигается, если действовать по описанному выше методу.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться