算法每日一题——第六天——干草堆（差分）

原题链接：2041. 干草堆 - AcWing题库

读完这道题大致可以把题分为两部分，第一部分需要统计每个干草堆所堆放的干草捆的数量，第二部分需要根据干草捆的数量对干草堆排序，输出排最中间的干草堆堆放的干草捆数量。

在统计干草捆数量时，我最开始使用的是暴力法直接统计（两层循环），时间复杂度为O( )，执行最后的样例时超时了。所以这道题需要使用差分法来解决。

差分法

差分就是将数列的每一项分别与前一项做差

例如：

   原序列：[ 2 , 4 ,  3 , 7 ,  6 , 8 ,  3 , 5 ]

差分序列：[ 2 , 2 , -1 , 4 , -1 , 2 , -5 , 2 , -5]

序列的第一个数与原序列相同(相当是第一个数减0)

差分序列比原序列多一个数(相当是0减去最后一个数)

性质:

(1)差分序列想要得到原序列,只需要 a[ i ] = a[ i ] + a[ i - 1 ]

(2)想原序列m位置到n位置的所有数加上x,只需在差分序列a[ m ] + x    a[ n + 1 ] - x

继续用上面的例子:

    原序列:[ 2 , 4 ,  3 , 7 ,  6 , 8 ,  3 , 5 ]

差分序列：[ 2 , 2 , -1 , 4 , -1 , 2 , -5 , 2 , -5]

要使第三个数到第七个数全部加2,a[ 2 ] + 2 , a[ 7 ] - 2

差分序列变为：[ 2 , 2 , 1 , 4 , -1 , 2 , -5 , 0 , -5]

化为原序列 :[ 2 , 4 , 5 , 9 , 8 , 10 , 5 , 5 ]

优点(使用范围)

给你多个区间, 要使每个区间范围内的数都加x,如果全部拿循环完成,时间复杂度为   , 若使用差分法,复杂度变为O(n)

这道题的第二部分需要根据干草捆的数量对干草堆排序，输出排最中间的干草堆堆放的干草捆数量。如果使用冒泡排序的话,时间依旧会超,我直接使用的是qsort函数。

下面是完整代码:

#include<stdio.h>
int cmp_int(const void* x,const void* y)
{
    return *((int*)x)-*((int*)y);
}
int main()
{
    int n,k;
    int a,b;
    scanf("%d%d",&n,&k);
    int arr1[1000010]={0};
    for(int i=0;i<k;i++)//差分法
    {
        scanf("%d%d",&a,&b);
        arr1[a]++;
        arr1[b+1]--;
    }
    for(int i=2;i<n+1;i++)//将差分序列恢复为原序列
    {
        arr1[i]=arr1[i-1]+arr1[i];
    }
    qsort(arr1,n,sizeof(int),cmp_int);//直接使用qsort函数
    printf("%d",arr1[(n)/2]);
}