воскресенье, 19 сентября 2010 г.

133. Border.

Ссылка на задачу здесь.

В качестве разминочной эта задача очень даже ничего. Для решения её нам необходимо знать всего лишь как быстро отсортировать список отрезков по их началу и применить кое-какие общие рассуждения.
Для удобства сортировки и отсутствия желания писать компаратор можно воспользоваться стандартной структурой pair<int,int> где будет хранится начальная и конечная точки отрезка.
Имея отрезки отсортированными очевидно, что взяв некий i-тый отрезок не один из последующих отрезков не может располагаться левее, в данном случае можно точку начала отрезка можно перенести на последующий отрезок, а в качестве конца выбрать max из координат концов. Логику работы можно проследить на следующем куске кода:


  1.   sort(mas.begin(),mas.end());
  2.   int answer = 0;
  3.   int begin = mas[0].first;
  4.   int end = mas[0].second;
  5.  
  6.   for(int i=1;i<mas.size();i++)
  7.   {
  8.     if (mas[i].second < end)
  9.       answer ++;
  10.     else
  11.       if (mas[i].first > begin)
  12.       {
  13.         begin = mas[i].first;
  14.         end = mas[i].second;
  15.       }
  16.       else end = mas[i].second;
  17.   }
* This source code was highlighted with Source Code Highlighter.
Полный код решения задачи - здесь.

Комментариев нет:

Отправить комментарий