原题链接:校门外的树
解题思路:
这里要注意到500,其实一共有501棵树,总数等于a+1(L+1)
参考代码:
#include<iostream>
#include <algorithm>
#include<vector>
using namespace std;
bool compare(const vector<int>& a,const vector<int>& b){
return a[0]<b[0];
}
int main()
{
int a,b;
cin>>a>>b;
vector<vector<int>> an;
int index=0;
while(index<b){
vector<int> anc(2);
cin>>anc[0]>>anc[1];
an.push_back(anc);
index++;
}
//排序是必须的
sort(an.begin(),an.end(),compare);
for(int i=0;i<b-1;i++){
//三种情况
//两个区间相交类似an[i]为(100,200)和an[i+1]为(150,300)这种情况下合并区间an[i+1]为(100,300)
if(an[i][1]>an[i+1][0]&&an[i][1]<an[i+1][1]){
an[i+1][0]=an[i][0];
// 两个区间重合类似an[i]为(100,200)和an[i+1]为(105,150)这种情况下an[i]为(105,150)没有参考价值直接使用an[i+1]为(100,200)覆盖掉
}else if(an[i][1]>an[i+1][0]&&an[i][1]>an[i+1][1]){
an[i+1][0]=an[i][0];
an[i+1][1]=an[i][1];
// 两个区间完全不相交类似an[i]为(100,200)和an[i+1]为(300,450)这种情况下(100,200)可以直接计算结果
}else if(an[i][1]<an[i+1][0]){
a-=an[i][1]-an[i][0]+1;
}
}
//处理最后一个特殊情况
a-=an[b-1][1]-an[b-1][0]+1;
cout<<a+1<<endl;
return 0;
}0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复