#include <iostream>
using namespace std;
struct Area{
int start;
int end;
}area[3];
int main(int argc, char** argv) {
int L=0,M=0;//长度,区间
cin>>L>>M;
for(int i=0;i<M;i++){ cin>>area[i].start>>area[i].end; }
for(int i=0;i<M;i++){
if(-1==area[i].start) continue;
for(int j=i+1;j<M;j++){
if(-1==area[j].start) continue;
if(area[i].start>area[j].end || area[i].end<area[j].start){
continue; //在左右两侧
}else if(area[i].start<=area[j].start && area[i].end>=area[j].end){
continue;//j包含在内侧
}else if(area[i].start>=area[j].start && area[i].end<=area[j].end){
area[i].start=area[j].start, area[i].end=area[j].end;
area[j].start=area[j].end = -1;
continue;//j包含在外部
}else if(area[i].start>=area[j].start && area[i].start<=area[j].end){
//在左侧相交
area[i].start=area[j].start;
area[j].start = area[j].end = -1;
continue;
}else if(area[i].end>=area[j].start && area[i].end<=area[j].end){
//在右侧相交
area[i].end=area[j].end;
area[j].start = area[j].end = -1;
continue;
}
}
}
int num=L+1;//树的总数
for(int i=0;i<M;i++){
if(area[i].start!=-1){
//树的总数减去移去的树,等于剩余的树
num -=area[i].end-area[i].start+1;
}
}
cout<<num;
return 0;
}
by kyouohou @ 2018-11-29 16:08:42
我的思路是将所有相交段连在一起,然后判断不相及交段中树的个数,只能过两个样例,咋回事啊!
by kyouohou @ 2018-11-29 16:09:05