mean

给定n个整数，从中选出m个整数出来，使得这m个整数两两求（差的绝对值），并保证（差的绝对值）之和最小。

analyse

首先，要使得m个数（差的绝对值）之和最小，易知这m个数应该是连续的，所以先排序。

然后就是滑窗法了。

滑的时候如何维护滑块的sum呢？

如果我们选出的数是：

  a1 a2 ... ak

对于a1，后面有k-1个数，且每个数都是减去它，即：a1带了k-1次负号;

对于a2，后面有k-2个数，且每个数都是减去它，，带了k-2次负号，但是他还要减去它前面的所有数，又带了k-1次正号，相抵后总的带了k-3次负号;

对于a3，后面有k-3个数，且每个数都是减去它，，带了k-3次负号，但是他还要减去它前面的所有数，又带了k-2次正号，相抵后总的带了k-5次负号;

...

由此可以看出，求m个数（差的绝对值）之和的方式是：

  sum1 = a1*(1-k) + a2*(3-k) + a3*(5-k) + ... + ak*(k-1)

向后滑动一个数，sum2的求法一样，这时我们来对比一下sum1和sum2的差别：

  sum1 = a1*(1-k) + a2*(3-k) + a3*(5-k) + ... + ak*(k-1)

  sum2 =            a2*(1-k) + a3*(3-k) + ... + ak*(k-3) + a(k+1)*(k-1)

我们先预处理出s[]数组，s[i]代表a0~ai的和.

那么：sum2=sum1+ai*(k-1)-a(i-k)*(1-k)-2*(s[i-1]-s[i-k]).

time complexity

O(N)

view code

 

#include 
     
      using namespace std;const int N=100010;int a[N],s[N];int main(){   freopen("G:\\nowcoder\\in","r",stdin);   freopen("G:\\nowcoder\\out","w",stdout);   int n,k,T;   scanf("%d",&T);   while(T--)   {       scanf("%d %d",&n,&k);       for(int i=0; i