值周
题目描述
JC内长度为L的马路上有一些值周同学,每两个相邻的同学之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,…L,都有一个值周同学。 由于水宝宝有用一些区间来和ssy搞事情,所以为了避免这种事走漏风声,水宝宝要踹走一些区域的人。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的人(包括区域端点处的两个人)赶走。你的任务是计算将这些人都赶走后,马路上还有多少个人。
输入描述:
第一行有2个整数L和M,L代表马路的长度,M代表区域的数目,L和M之间用一个空格隔开。 接下来的M行每行包含2个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标
输出描述:
1个整数,表示马路上剩余的人的数目。
输入
500 3
150 300
100 200
470 471
输出
298
题目大意
和校门外的树差不多
思路
由于数据很大,暴力会超时,需要使用离散化,按左端点进行排序
只记录头尾,给重合的头尾进行补充,维护成最后互不重合的几个区间,最后进行减去。
#include<bits/stdc++.h> using namespace std; struct date{ long long int l=0; long long int r=0; }num[1000005]; int ans[10000]; int aa=0; bool cmp(date a,date b){ return a.l<b.l; } int main() { //每两个相邻同学间隔1米 //踹走一些区域的人 //这些区域用它们在数轴上的起始点和终止点表示。 //区域之间可能有重合的部分 //(包括区域端点处的两个人)赶走 //马路上还有多少个人。 long long int L,n; scanf("%lld%lld",&L,&n); long long int sum=L+1; for(int i=0;i<n;i++) { scanf("%lld%lld",&num[i].l,&num[i].r); } sort(num,num+n,cmp); long long int head=num[0].l; long long int fail=num[0].r; for(int i=1;i<n;i++) { if(num[i].l<=fail) { fail=max(fail,num[i].r); } else { ans[aa]=fail-head+1; head=num[i].l; fail=num[i].r; aa++; } } ans[aa]=fail-head+1; for(int i=0;i<=aa;i++) { //printf("%d %d\n",num[i].l,num[i].r); //printf("%d\n",ans[i]); sum=sum-ans[i]; } printf("%d",sum); return 0; }