On Segment's Own Points(可用区间长度)

本文主要是介绍On Segment's Own Points(可用区间长度)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=42180#problem/A

思路一：

排序合并，但是比较繁琐

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,l,r;
struct node
{
int l,r;
}pe[103];
bool cmp(node a,node b)
{
if(a.l==b.l)return a.r<b.r;
else return a.l<b.l;
}
int main()
{
while(~scanf("%d",&n))
{
int sum=0;
node hb[103];
scanf("%d%d",&l,&r);
for(int i=0;i<n-1;i++)
{
scanf("%d%d",&pe[i].l,&pe[i].r);
}
sort(pe,pe+n-1,cmp);
int t=0;
hb[0].l=pe[0].l;
hb[0].r=pe[0].r;
for(int i=1;i<n-1;i++)
{
if(hb[t].r<pe[i].l)
{
t++;
hb[t].l=pe[i].l;
hb[t].r=pe[i].r;
}
else if(hb[t].r<pe[i].r)
{
hb[t].r=pe[i].r;
}
}
for(int i=0;i<=t;i++)
{
if(hb[i].l>=l&&hb[i].r<=r)sum+=hb[i].r-hb[i].l;
else if(hb[i].l<=l&&hb[i].r>l&&hb[i].r<=r)sum+=hb[i].r-l;//中间那个判断忘了！！！！！！！
else if(hb[i].l>=l&&hb[i].l<r&&hb[i].r>=r)sum+=r-hb[i].l;
else if(hb[i].l<=l&&hb[i].r>=r){sum=r-l;break;}
//else if(hb[i].l>=r || hb[i].r<=l){sum+=0;}
}
if(n==1)printf("%d\n",r-l);
else
printf("%d\n",r-l-sum);
}
return 0;
}

思路二：

打表赋值0-1

#include<cstdio>
#include<iostream>
int mark[100+5]={0};
int main()
{int i,j,n,f1,s1,f,s,count=0;scanf("%d",&n);scanf("%d%d",&f1,&s1);for(i = f1; i < s1; i++)mark[i] = 1;for(i = 1; i < n; i++){scanf("%d%d",&f,&s);for(j = f; j < s; j++)mark[j] = 0;}for(i = f1; i < s1; i++)if(mark[i]==1)count++;printf("%d",count);return 0;
}

思路三：

++、--当flat为0的时候才累加长度

#include<stdio.h>
#include<string.h>
int flag[105];
int main (){
int n,m,a,b,s,e,sum,k;
int i,j;
while(scanf("%d",&n)!=EOF){
memset(flag,0,sizeof(flag));
scanf("%d%d",&s,&e);
for(i=1;i<n;i++){
scanf("%d%d",&a,&b);
flag[a]++,flag[b]--;
}
sum=0;
k=0;
for(i=0;i<=100;i++){
sum+=flag[i];
if(i>=s&&i<e&&sum==0)
k++;
}
printf("%d\n",k);
}
}