Сравнение priority_que и multiset

- priority_que работает за o(n), а multiset (nlogn)
- priority_que умеет делать только часть того, что делает multiset
  (искать/удалять максимум, минимум)

Резюме, если n такое, что nlogn успевает
- пользуйтесь multiset (или set если все элементы различны)

Объявление

priority_queue<int, vector<int>> PQ;      // верхний - максимальный

priority_queue<int, vector<int>, greater<int> > timeEvents;      // верхний - минимальный
priority_queue<int, vector<int>, greater<int> > distanceEvents;  //  -"-

Занесение

if (c == 'T')     timeEvents.push(x);
  else        distanceEvents.push(x);

distanceEvents.push(1000);

Проверка на непустоту
while(!timeEvents.empty() || !distanceEvents.empty())

Обращение к верхнему элементу
timeEvents.top()
distanceEvents.top()

Выталкивание верхнего элемента
timeEvents.pop();
distanceEvents.pop();

http://dl.gsu.by/task.jsp?nid=1266212&cid=130

14_JanS. SLOWDOWN

Бесси участвует в лыжной гонке через всю страну. Он начала движение
со скоростью 1 м/сек. Однако по мере уставания, она замедляет ход
по следующим правилам. После первого замедления её скорость становится
1/2 м/сек, после второго замедления - 1/3 м/сек и т.д.

Вам говорится когда и где Беси замедляется в терминах серии таких событий:

T 17
Означает, что Беси замедлилась в конкретное время после 17 секунд гонки.

D 10
Означает, что Беси замедлилась на дистанции 10 метров от старта.

По заданному списку из N таких событий (1 <= N <= 10,000), пожалуйста
определите количество времени в секундах, которое потребуется Беси,
чтобы преодолеть расстояние в 1 километр. Округлите свой ответ до
ближайшего целого (0.5 округляется к 1).

INPUT FORMAT:

• Строка 1: Значение N.
• Строки 2..1+N: Каждая строка имеет вид "T x" или "D x", указывая
  на событие по времени или событие по расстоянию. В обоих случаях,
  х - целое число. Гарантируется, что все события произойдут,
  прежде чем она пройдёт 1 км.
  Возможно такое, что несколько событий произойдут одновременно,
  вынуждая Беси замедляться "quite a bit all at once" (?сразу несколько раз).
  События могут идти не по порядку.

SAMPLE INPUT (файл slowdown.in):
2
T 30
D 10

INPUT DETAILS:
Беси замедлится в момент времени t=30 и на расстоянии d=10 метров.

OUTPUT FORMAT:

• Строка 1: Общее время, которое потребуется Беси, чтобы преодолеть
  расстояние в 1 км.

SAMPLE OUTPUT (файл slowdown.out):
2970

OUTPUT DETAILS:
Беси путешествует первые 10 метров со скоростью 1 м/сек, и это займёт у неё
10 секунд. Затем она замедлится до ? м/сек, и она потратит 20 сек на следующие
10 метров. В этот момент она достигнет отметки в 30 сек, где скорость уменьшится
до 1/3 м/сек. Оставшиеся 980 метров займут у неё 980*3 = 2940 сек.
Общее время = 10 + 20 + 2940 = 2970.

Идея решения:
Сразу по вводу создаём два массива событий
T - времён, в которые изменялась скорость
D - расстояний, на которых изменялась скорость
Сортируем их по возрастанию.
Добавляем в массив расстояний конечное расстояние.
Пока не кончился массив времён
Выбираем, какое событие (по времени или расстоянию) произойдёт раньше
Пересчитываем пройденный путь (Path) и затраченное время Time
Досматриваем массив расстояний.
Выводим вычисленное потраченное время Time

Авторское решение на С++, использующее priority_que

#include <bits/stdc++.h>
using namespace std;

int N;

priority_queue<int, vector<int>, greater<int> > timeEvents;
priority_queue<int, vector<int>, greater<int> > distanceEvents;

double currentD;
double currentT;
int speedValue; // 1/speed

int main()
{
    ifstream in ("slowdown.in");
    ofstream out ("slowdown.out");

    in >> N;
    for (int i = 0; i < N; i++)
    {
        char c;
        int x;
        in >> c >> x;
        if (c == 'T') timeEvents.push(x);
          else        distanceEvents.push(x);
    }
    distanceEvents.push(1000);

    currentT = currentD = 0.0;
    speedValue = 1;

    while(!timeEvents.empty() || !distanceEvents.empty())
      {
        bool isNextTime = false;
          if(distanceEvents.empty())   isNextTime = true;
              else if(!distanceEvents.empty() && !timeEvents.empty())
                     if (timeEvents.top() < (currentT + (distanceEvents.top() - currentD)*speedValue))
                       isNextTime = true;
           if(isNextTime)  {
                             currentD += (timeEvents.top() - currentT) / (speedValue + 0.0);
                             currentT = timeEvents.top();
                             timeEvents.pop();
                           }
             else
                           {
                             currentT += (distanceEvents.top() - currentD) * speedValue;
                             currentD = distanceEvents.top();
                             distanceEvents.pop();
                           }
        speedValue++;
      }

    int currentTime = (int) currentT;
    double fraction = currentT - currentTime;
    if(fraction < 0.5) out << currentTime;
      else             out << currentTime + 1;
}