题解 P1047 【校门外的树】

melonlemon · 2019-03-18 21:04:59 · 题解

写了一个简单的程序，时间复杂度为O(MlogM),主要是对M条马路进行排序。 大体的思路就是先对M条马路根据起始点排序。将起始点0作为当前点。 遍历所有的马路，对每条马路进行判断。 当前点在马路起始点前面，就可以直接计算空余的树的数目为起始点-当前点， 更新起始点为马路结束点+1. 如果当前点在马路中间，更改当前点为马路结束点+1 如果当前点在马路后面（因为重叠可能出现包含？），continue。 最后更新空余的树的数目为 L - 当前点 + 1. 代码如下：

#include<iostream>
#include<algorithm>

using namespace std;
struct Edge
{
    int start;
    int end;
};
Edge path[101] ;
bool InPath(int Pos, int PathNo)
{
    return Pos >= path[PathNo].start && Pos <= path[PathNo].end;
}
int main(int argc, char const *argv[])
{
    int L, M;
    cin >> L >> M;
    int start, end;
    for (int i = 0; i < M; ++i)
    {
        cin >> path[i].start >> path[i].end;
    }
    sort(path, path + M, [](const Edge & lobj, const Edge & robj)->bool
    {
        return lobj.start < robj.start;
    });
    int count = 0;
    int curPos = 0;
    for (int i = 0; i < M; ++i)
    {
        if (curPos > path[i].end)
        {
            continue;
        }
        else if (InPath(curPos, i))
        {
            curPos = path[i].end + 1;
        }
        else
        {

            count += path[i].start - curPos;
            curPos = path[i].end + 1;
        }
    }
    count += L - curPos + 1;
    cout << count << endl;
    return 0;
}