题解 P2434 【[SDOI2005]区间】

蹲在丛中笑 · 2017-11-22 22:49:24 · 题解

震惊地发现竟然还没有人贴差分的题解。。

没错，就像楼下某位大佬说的，每次输入x和y，于是x的度++，y的度--

然后再扫一遍，累积从0到+的就是左端点，从+到0的就是右端点。

时间复杂度O（1e6）

貌似不是很优越？

总之代码很短很好写

#include<stdio.h>
#define N 1000005
int n,x,y,cnt,a[N],b[N];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&x,&y);
        a[x]++; b[y]++;
    }
    for(int i=1;i<N;i++) {
        if(!cnt&&a[i]) printf("%d ",i);
        cnt+=a[i]-b[i];
        if(!cnt&&b[i]) printf("%d\n",i);
    }
}