画展布置

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
//双指针就尽量往O（n）方向想，不然双循环必超时。
//好像排序之后，选任意两个点找最小的就可以了吧，因为递增序列任意两个之间肯定是最小的啊，在利用双指针找两个数就行了吧,不对因为是要找M个数，所以还是是要找一个子数组到达M个，
//注意优化的点，b增加后，a指针移动后，只需要减去剔除的元素差，加上新进来的元素差就可以了,这样时间复杂度就是On了，避免重复计算

int compare(const void*p1,const void *p2)
{
    return *(int*)p1-*(int*)p2;
}
int main() {
    int N,M;
    scanf("%d %d",&N,&M);
    int array[N];
    for(int i=0;i<N;i++)
    {
        scanf("%d",&array[i]);
    }

    //排序一下
    qsort(array, N, sizeof(int), compare);
    long long min_L;   //记录最小L,结果可能会很大，所以必须用longlong
    int a=0,b=0+M-1; //设定一个窗口
    //先统计第一个窗口的值
    long long temp_L=0;
    for (int i=a;i<=b-1&&b<=N-1; i++) {
        temp_L += (long long)array[i+1] * array[i+1] - (long long)array[i] * array[i];
    }
    min_L=temp_L;
    //统计剩余窗口
    a++;
    b++;
    while (b<=N-1) {
       // long temp_L=0;
            //对哦，我怎么就没想到呢，只需要减去剔除的元素差，加上新进来的元素差就可以了,这样时间复杂度就是On了，避免重复计算

        temp_L -= (long long)array[a] * array[a] - (long long)array[a-1] * array[a-1];
        temp_L += (long long)array[b] * array[b] - (long long)array[b-1] * array[b-1];
        
        if (temp_L<min_L) {
            min_L=temp_L;//统计最小
        }
        a++;//滑动到下一个窗口
        b++;
    }
    
    printf("%lld",min_L);
    return 0;
}