[codeforces1366B]Shuffle区间交叠+区间合并

Educational Codeforces Round 89 (Rated for Div. 2)  参与排名人数13281

[codeforces 1366B]     Shuffle   区间交叠+区间合并

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址https://codeforces.com/contest/1366/problem/B

 题目大意：给定一个数组，除位置x处的元素值为1外，其它元素值均为0，

按先后顺序给出区间，请注意，前面的操作，会对后面的区间有影响。

若该操作区间，存在元素值为1的元素，那么该区间，通过交换操作，所有元素值都可以设置为1。

计算最多有几个数可以设置为1.

样例模拟如下

6 4 3
1 6
位置4在位置区间[1,6]中，故位置1,2,3,4,5,6,这6个数都能取到1个数都能取到1
2 3
5 5
输出6
4 1 2
2 4
1 2
位置1在位置区间[1,2]中，故位置1，位置2，这2个数都能取到1
故位置1,2均能取到1
输出2
3 3 2
2 3
位置3在位置区间[2,3]中，故位置2，位置3，这2个数都能取到1
1 2
请注意，前面的区间操作，对后面的区间操作有影响，
位置2在位置区间[1,2]中，故位置1，位置2，这2个数都能取到1
故位置1,2,3均能取到1
输出3

区间交叠情况如下，可结合AC代码进行研究

区间合并情况如下，可结合AC代码进行研究

AC代码如下

#include
#include
using namespace std;
int a[110],b[110];
int main(){
int t,n,x,m,i,l,r,flag,k;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&x,&m);
flag=0,k=0;//请注意k=0
for(i=1;i<=m;i++){
scanf("%d%d",&a[i],&b[i]);
if(!flag&&a[i]<=x&&x<=b[i])k=i,flag=1;//按顺序，找x出现的第一个区间
}
l=a[k],r=b[k];//若此时k==0,表示没找到x出现的区间。
for(i=k+1;i<=m;i++){
if(b[i] if(r l=min(l,a[i]);//区间合并
r=max(r,b[i]);//区间合并
}
printf("%d\n",r-l+1);
}
return 0;
}