Решение задачи "Закраска прямой" с Меньшиков

Без пояснения   Просмотров: 22


На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка (Li и Ri). Найти длину окрашенной части числовой прямой.

Код

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct point
{
    int value;
    bool isBegin;
    point(){}
    point(int _value, bool _isBegin)
    {
        value = _value;
        isBegin = _isBegin;
    }
};
int n;
vector<point> mas;
void input()
{
    cin>>n;
    mas.resize(2*n);
    int begin,end;
    for (int i=0;i<2*n;i+=2)
    {
        scanf("%d %d",&begin, &end);
        mas[i]   = point(begin,true);
        mas[i+1] = point(end,false);
    }
}
bool cmpPoint(const point &a, const point &b)
{
    if (a.value != b.value)
        return a.value < b.value;
    if (a.isBegin && !b.isBegin)
        return true;
    return false;
}
void solve()
{
    sort(mas.begin(),mas.end(),cmpPoint);
    int totalLen = 0;
    int segmAmount = 1;
    int prev = mas[0].value;
    for (int i=1;i<mas.size();i++)
    {
        if (segmAmount != 0)
            totalLen += mas[i].value - prev;
        prev = mas[i].value;
        if (mas[i].isBegin)
            segmAmount++;
        else
            segmAmount--;
    }
    cout<<totalLen;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
   
    input();
    solve();
    return 0;
}

         

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


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

Комментарии

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