Problem's Link
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 <bits/stdc++.h> 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<n; ++i) scanf("%d",&a[i]); sort(a,a+n); s[0]=a[0]; for(int i=1; i<n; ++i) s[i]=s[i-1]+a[i]; long long sum=0,cnt=1-k; for(int i=0; i<k; ++i) { sum+=a[i]*cnt; cnt+=2; } long long res=sum,l=0; for(int i=k; i<n; ++i) { sum-=a[l]*(1-k); sum+=a[i]*(k-1); sum-=2*(s[i-1]-s[l]); res=min(res,sum); ++l; } printf("%lld\n",res); } return 0; }
