题解 | #值周#

值周

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

思路:差分+离散化,将题目里涉及的点可以离散化为1,2,3,4,5.....这样的数组的下标,在离散化的同时还要记录对这个点的操作,如果是去除一人就在这下标+1,然后再在这个下标位置后m个地方记录-1的点来保证后面的数不受影响.

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2000010;

int n,m;
struct alls{
	int x,y;
}all[N];

bool cmp(alls a,alls b){
	return a.x<b.x;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		all[i]={a,1};
		all[i+m]={b+1,-1};
	}
	all[2*m+1]={n+1,1};//把总长度存入,记得加1,表示n+1以内的树有多少
	sort(all+1,all+2*m+2,cmp);
	int a=0;//差分,表示操作过的次数
	int cnt=0;//存结果
	for(int i=1;i<=2*m+1;i++)
	{
        
		a+=all[i].y;
		if(a==1 && all[i].y==1)//当a从0变为1,并且在要对某个区间进行去除操作时,先把前一段没进行过操作的区间的数加起来
		cnt+=all[i].x-all[i-1].x;
	}
	
	cout<<cnt<<endl;
	
	return 0;
}
全部评论

相关推荐

06-07 00:00
已编辑
腾讯_后端开发
点赞 评论 收藏
分享
zzzzhz:兄弟你先猛猛投简历至少三百家,能约到面试就去面。最近可以速成智能小车,智慧家居烂大街的项目,不需要自己写,只需要把里面的代码讲解看明白就行。把其中涉及到的八股文都拿出来单独背一下,我去年找工作就一个智能小车智慧家居找了10k差不多。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务