目录
题目
思路
常规暴力
离散化
代码
题目
题目描述
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入
输入的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出
输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
样例输入
500 3 150 300 100 200 470 471样例输出
298
学校oj SWUST OJ#149
洛谷
思路
常规暴力
可以来一个模拟，根据总长度，设一个数轴，每一个点初始值为1代表有树
for(int i=0;i<=L;i++) a[i]=1;
/*L为马路(即数轴)总长注：题目要求从0开始 */然后m次询问，每一次一个起点和终点，然后把这些范围内每个点，赋值为0，代表砍了树。
for(int i=l;i<=r;i++) a[i]=0;
//l代表起点，r代表终点最后统计值为1的有多少即为答案（这里可前缀和，也可正常sum加）
for(int i=1;i<=L;i++) a[i]+=a[i-1];
cout<<a[L]<<endl;
//前缀和,注意是从i=1开始加，防爆
int sum=0;
for(int i=0;i<=L;i++) sum+=a[i];
cout<<sum<<endl;
//正常加法,这里就是从0开始了离散化
如果说，马路的长度是超过long long范围，或者说无限长。
还这样模拟的话，就出问题了。超时不说，超数组定义范围这是肯定的（根本就不给机会模拟）
升级版校门外的树---火烧赤壁
将数据先画出来，如果我们去做，一眼就可以看出砍的树是100-300之间和470-471。所以加起来即203(算上端点）显然，我们是这么算的：
(200-100+1)+(300-150+1)+(471-470+1)-(200-150+1)。
其中红色部分是重复的阴影区，蓝色是端点。
所以根据以上案例：即把每一段区间都加起来，再减去重复，再加上端点，即为砍的树的总和。
但是，如果说，把样例换一下顺序：
500 3 100 300 150 200 470 471
那么这样画出来的图就是这样的：
这样我们可以发现，阴影部分被完全包围了。按照刚才的做法
(300-100+1)+(200-150+1)+(470-471+1)-(200-150+1)。
就会发现重复了。但是我们是知道重复，电脑不知道呀。(可以打flag记录，但没必要）
当然，样例只是3个数据，实际检测时有可能会涉及很多数，难免不会遇到上面这种重复的情况。
所以，我们不妨将起点的a数组从小到大排序，终点的b数组从小到大排序，然后a[i]，b[i]一一对应，就可以避免重复，变成最开始样例的形式。
这样，从小到大排序一下，就可以避免刚才完全被包含的情况。同样，按照之前的做法
(-5-(-20)+1)+(20-(-10)+1)+(100-0+1)+(400-150+1)-(-5-(-10)+1)-(20-0+1)。
我们可以发现，前面加的部分，他们b[ i ],a[ i ]对应的 i 是相同的，而后面减去的他们的 i 是刚好相差1的。
这也就是刚才排序的原因之一，可以说是一箭双雕了，即避免完全重复，也一一对应了。
实现代码如下：
for(int i=1;i<=m;i++) {sum+=b[i]-a[i]+1;//前面相加部分,+1是端点if(a[i]<b[i-1]&&i!=1) {sum-=b[i-1]-a[i]+1;//后面相减部分,+1是端点/* 当i=1时，第一次就不用减了(防爆)先判断，如果a[i]>=b[i-1]就说明没有重复部分就不用再减了 */}
}代码
暴力
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int a[10005];
int main() {int L,m;cin>>L>>m;for(int i=0;i<=L;i++) a[i]=1;while(m--) {int l,r;cin>>l>>r;for(int i=l;i<=r;i++) a[i]=0;}/* 正常加法int sum=0;for(int i=0;i<=L;i++) sum+=a[i];cout<<sum<<endl; *///前缀和for(int i=1;i<=L;i++) a[i]+=a[i-1];cout<<a[L]<<endl;return 0;
}离散化
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int a[10005],b[10005];
int main() {ll L,m;cin>>L>>m;//ll为long long 简写for(int i=1;i<=m;i++) cin>>a[i]>>b[i];sort(a+1,a+m+1);sort(b+1,b+m+1);ll sum=0;for(int i=1;i<=m;i++) {sum+=b[i]-a[i]+1;if(a[i]<b[i-1]&&i!=1) {sum-=b[i-1]-a[i]+1;}}cout<<L+1-sum<<endl;return 0;
}