Матч 391, Снежная зима (SnowyWinter)

Дивизион 2, Уровень 1

Имеется трасса, частями покрытая снегом. Массивы startPoints и endPoints содержат начала и концы отрезков, занесенных снегом. Необходимо вычислить общую длину трассы, покрытую снегом. Отрезки (startPoints[i], endPoints[i]) могут перекрываться.

Класс: SnowyWinter

Метод: snowyHighwayLength(vector<int> startPoints,

vector<int> endPoints)

Ограничения: startPoints и endPoints содержат одинаковое количество элементов, от 1 до 50, 1 £ startPoints[i], endPoints[i] £ 20, startPoints[i] < endPoints[i].

Вход. Два массива startPoints и endPoints, описывающие координаты начал и концов отрезков.

Выход. Общая длина трассы, покрытая снегом.

Пример входа

startPoints	endPoints
{17,85,57}	{33,86,84}
{45,100,125,10,15,35,30,9}	{46,200,175,20,25,45,40,10}

Пример выхода

44

132

РЕШЕНИЕ

обработка массивов

Представим каждый отрезок в виде пары (startPoints[i], endPoints[i]), занесем их в массив v и отсортируем по координате начала. В конец массива занесем фиктивный отрезок (+µ, +µ). Двигаемся по отрезкам слева направо. Если начало следующего отрезка больше конца текущего, то прибавляем длину текущего отрезка к сумме. Иначе увеличиваем правый конец текущего отрезка до правого конца следующего.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class SnowyWinter

{

public:

int snowyHighwayLength(vector<int> startPoints, vector<int> endPoints)

{

int i, b, e, res;

vector<pair<int,int> > v;

for(res = i = 0; i < startPoints.size(); i++)

v.push_back(make_pair(startPoints[i],endPoints[i]));

sort(v.begin(),v.end());

v.push_back(make_pair(2000000000,2000000000));

b = e = -1;

for(i = 0; i < v.size(); i++)

{

if (v[i].first > e)

{

res += e - b;

b = v[i].first; e = v[i].second;

}

else e = max(e,v[i].second);

}

return res;

}

};