差分法求解人类识别审查

解题思路:

如果我们假设有K个人，那么K就得在题目中所给的n个范围中的K个，那么，我们可以分别统计从1到n每个数在题目给的n个范围中出现的次数（即有多少人说了真话），我们设这个数组为cover,比如cover{1}代表1这个数在题目中n个范围中出现的次数。比如说我们最后求出来是k，那它对应的cover[k]就是k符合多少个范围，即有多少人说了真话，那么可以知道k=cover[k],所以我们只要求满足这个条件的所有cover的最大值。思路就是这样，那我们如何实现？第一步，如何统计。如果我们分别扫描这n个范围，再分别给这n个范围里面的数逐个加一，很容易就超时，所以要用差分法。定义一个数组cha，cha[i]=cover[i]-cover[i-1];cha[0]=cover[0];

那么cover[i]就等于cha的前i+1项和，就是从cha[0]一直加到cha[i];比如说现在有一个范围【a,b】;因为我会在处理完这n个范围后累加求cover，那我给cha[a]加上1是不是就相当于给cover[a]以及后面所有的cover都加上1，那我再给cha[b+1]减1，是不是就相当于给cover[b+1]以及后面所有的cover[i]减1，经过这两个处理，我们成功实现了给cover[a]到cover[b]加1，时间复杂度直接降为O(n）；好，处理完这n个范围后我们就可以累加求cover，然后找满足cover[k]=k并且k最大的k值即可。
注意事项：当找不到满足这样的k值时候要输出-1。

参考代码:

#include<stdio.h>

int main(){

    int n;

    scanf("%d",&n);int cover[100005]={0};int cha[100005]={0};

    for(int i=0;i<n;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        cha[a]+=1;cha[b+1]-=1;

    }int sum=0;int max=-1;

    for(int i=0;i<=n;i++){

        sum+=cha[i];

        cover[i]=sum;

        if(max<sum&&sum==i)max=sum;

    }

   if(max>=0)printf("%d",max);

   else{printf("-1");}

    return 0;

}