蓝桥杯2025年第十六届省赛真题

解题思路:

先对画作价值升序排序，因为连续的 M 个元素按升序排列时，相邻平方差的绝对值之和最小。

利用数学裂项相消原理，升序排列的连续 M 个元素的相邻平方差和 = 区间最大值平方 - 区间最小值平方，无需逐一遍历求和，简化计算。

注意事项:用long long存储平方值和 L 值，避免 int 类型存储大数值（如 10⁵的平方 = 10¹⁰）时溢出。

参考代码：

#include<stdio.h>

#include<limits.h>

#include<stdlib.h>  

/*qsort()需要的头文件，c语言的包含在头文件的函数不用用户自定义。

c++里头文件包含sort（）函数，两个都是快速排序，默认升序，解决超时问题的关键中的关键

*/

int cmp(const void *a, const void *b) {    

    return *(const int*)a - *(const int*)b;

}

int main(){    

    int N,M,i,j;    

    scanf("%d%d",&N,&M);        

     int arr[N];    

    for(i=0;i<N;i++){        

    scanf("%d",&arr[i]);   

    }      

    qsort(arr, N, sizeof(int), cmp);   

//数据比较大时一定要用long long   

    long long min_L = LLONG_MAX;    

    for(i=0;i<=N-M;i++){       

         int end = i + M - 1; 

//关键在于保证首尾相差M幅画的连续区间，   

        long long square_end = (long long)arr[end] * arr[end];       

         long long square_start = (long long)arr[i] * arr[i];       

         long long current_L = square_end - square_start;       

         if(current_L < min_L){            

        min_L = current_L;       

         }   

    }   

  if(M == 1) min_L = 0;   

  printf("%lld\n",min_L);      

 return 0;

}