[NOIP2005]校门外的树

校门外的树

https://ac.nowcoder.com/acm/problem/16649

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

该题妥妥的枚举题，枚举优化只要在于减少枚举次数。

对于不同的数据范围，采用不同的求解思路。

先看看数据范围：L（1 <= L <= 10000）和 M（1 <= M <= 100）

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

方法1：暴力枚举

数据不算太大，枚举即可。

有一个优化方法--合理的维护数据。代码如下：

#include <bits/stdc++.h>
using namespace std;
int arr[10005] = { 0 };
int L,M,i,j;
int main()
{
    scanf("%d%d",&L,&M);
    for (i = 0;i < M;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        for (j = x;j <= y;j++)
            if (arr[j] == 0)
            {
                L--;
                arr[j] = 1;
            }
    }
    cout << L + 1;
    
    return 0;
}

写该题的时候有两次WA。

第一次WA，想到了一个更好的数据维护方法，减少了时间复杂度。

第二次WA，有一个启示，主要是尽量减少在for循环中定义变量，直接在全局或者main函数里面定义即可。

方法2：差分+前缀和

如果扩大数据范围：1 <= L <= 100000和1 <= M <= 100000；如果使用原来的思路--暴力枚举，时间复杂度过大，会有超时的风险，因此变换思路，减少时间复杂度.

方法二使用差分，将对区间的修改改为对区间端点的修改。

#include <bits/stdc++.h>
using namespace std;
int delta[10005] = { 0 };
int L,M,i,j;
int main()
{
    scanf("%d%d",&L,&M);
    for (i = 0;i < M;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if (x > y)
            swap(x,y);
        delta[x]++;
        delta[y + 1]--;
    }
    int a = 0,cnt = 0;
    for (i = 0;i <= L;i++)
    {
        a += delta[i];
        if (a == 0) cnt++;
    }
    cout << cnt;
    
    return 0;
}

方法3：合并区间。

#include <bits/stdc++.h>
using namespace std;
int L,M,i;
struct ty
{
    int x;
    int y;
}a[105];
bool comp(ty a,ty b)
{
    if (a.x < b.x) return 1;
    return 0;
}
int main()
{
    scanf("%d%d",&L,&M);
    for (i = 1;i <= M;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a + 1,a + 1 + M,comp);
    int cnt = L + 1;
    int l = a[1].x,r = a[1].y;
    for (i = 2;i <= M;i++)
    {
        if (a[i].x < r)
            r = max(r,a[i].y);
        else
        {
            cnt -= (r - l + 1);
            l = a[i].x;
            r = a[i].y;
        }
    }
    cnt -= (r - l + 1);
    cout << cnt;
    
    return 0;
}

方法4：差分+前缀和+离散化(扫描线操作)

如果继续扩大范围：1 <= L <= 10^9和1 <= M <= 100000怎么办呢？、

使用差分-前缀和加上离散化思想，将方法二的差分方法进一步优化。

#include <bits/stdc++.h>
using namespace std;
int l,m;
struct ty
{
    int pos; //位置，将数轴离散化，减少空间复杂度
    int num; //差分数组
}delta[210] = { 0 };
bool comp(ty a,ty b)
{
    if (a.pos == b.pos) return a.num < b.num;
    return a.pos < b.pos;
}
int main()
{
    scanf("%d%d",&l,&m); //L--马路的长度 M--挖树的次数
    for (int i = 1;i <= m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        delta[i].pos = x;
        delta[i].num = 1;
        delta[i + m].pos = y + 1;
        delta[i + m].num = -1;
    }
    sort(delta + 1,delta + (2 * m) + 1,comp); //按位置在数轴上排序（从小到大）
    int cnt = 0; //记录次数
    int a = 0;
    for (int i = 1;i <= 2 * m;i++)
    {
        a += delta[i].num;
        if (a == 1 && delta[i].num == 1)
            cnt += delta[i].pos - delta[i - 1].pos;
    }
    cnt += l - delta[2 * m].pos + 1;
    cout << cnt;
    
    return 0;
}