1931【05NOIP普及组】校门外的树时间限制: 1000 ms 内存限制: 65536 KB提交数: 9210 通过数: 6928【题目描述】某校大门外长度为L的马路上有一排树每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴马路的一端在数轴00的位置另一端在LL的位置数轴上的每个整数点即001122……LL都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数区域之间可能有重合的部分。现在要把这些区域中的树包括区域端点处的两棵树移走。你的任务是计算将这些树都移走后马路上还有多少棵树。【输入】第一行有两个整数L1≤L≤10000L1≤L≤10000和 M1≤M≤100M1≤M≤100LL代表马路的长度MM代表区域的数目LL和MM之间用一个空格隔开。接下来的MM行每行包含两个不同的整数用一个空格隔开表示一个区域的起始点和终止点的坐标。【输出】一行这一行只包含一个整数表示马路上剩余的树的数目。【输入样例】500 3 150 300 100 200 470 471【输出样例】298【提示】【数据规模】对于20%的数据区域之间没有重合的部分对于其它的数据区域之间有重合的情况。思路我没有想到什么很高明的方法我是这样想的首先定义一个长度为L的数组a然后数组a里的每一项都归0然后读入区间最左边为L最右边为r数组a[L]~a[r]全部变为1然后统计看有几个为0就好了今天是2026年7月18日对这个题解进行更新懒得写思路新代码可以处理数据更大的情况大概就是一个什么区间合并什么的我很懒所以没有思路没准每天有空了我会回来写的不过应该不可能代码#include bits/stdc.h using namespace std; int main(){ long long l,m,u,uu,b0; cinlm; long long a[l10]{0}; for(int j1;jm;j){ cinuuu; for(int iu;iuu;i){ a[i]1; } } for(int i0;il;i){ if(a[i]0){ b; } } coutb; return 0; }//这是新代码 #includebits/stdc.h using namespace std; struct aa{ long long u,v; }; bool cmp(aa a,aa b){ return a.ub.u; } int main(){ long long l,m; cinlm; aa a[m10]; for(int i1;im;i){ cina[i].ua[i].v; } sort(a1,am1,cmp); long long cnt1LL*a[1].v-1LL*a[1].u1; for(int i2;im;i){ if(a[i].va[i-1].v){ cnt1LL*a[i].v-1LL*a[i].u1; long long cha0; if(a[i].ua[i-1].v){ chaa[i-1].v-a[i].u1; a[i].vmax(a[i].v,a[i-1].v); } cnt-cha; }else{ a[i].va[i-1].v; } } cntl-cnt1; coutcnt; return 0; }
