Minimum Sum（思维）-布布扣-bubuko.com

Description

There are n numbers A[1] , A[2] .... A[n], you can select m numbers of it A[B[1]] , A[B[2]] ... A[B[m]] ( 1 <= B[1] < B[2] .... B[m] <= n ) such that Sum as small as possible.

Sum is sum of abs( A[B[i]]-A[B[j]] ) when 1 <= i < j <= m.

Input

There are multiple test cases. First line of each case contains two integers n and m.( 1 <= m <= n <= 100000 ) Next line contains n integers A[1] , A[2] .... A[n].( 0 <= A[i] <= 100000 ) It‘s guaranteed that the sum of n is not larger than 1000000.

Output

For each test case, output minimum Sum in a line.

Sample Input

4 2 5 1 7 10 5 3 1 8 6 3 10

Sample Output

2 8

题解：题意就是求连续m个数字相互差的绝对值最小；

刚开始就想着先排序，从大到小模拟了下找到了3x1+x2-x3-3x4;由此可以看出规律；但是由于想着数据是1e5，就不敢写。。。然后队友写了下就过了。。。吊。。。其实是因为当N是1e5的时候，如果M也很大，那么i是从n-m开始的，所以也没啥事；

然后的思路就是从后往前大暴力。。。

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN = 100010;
 7 int A[MAXN];
 8 int main(){
 9     int n,m;
10     while(~scanf("%d%d",&n,&m)){
11         for(int i = 0; i < n; i++){
12             scanf("%d",&A[i]);
13         }
14         sort(A, A + n);
15         int ans = 0x3f3f3f3f;
16         for(int i = n - m; i >= 0;i--){
17             int x = m - 1, temp = 0;
18             for(int j = i + m - 1; j >= i;j--){
19                 temp += x * A[j];
20             //    printf("x = %d a[%d] = %d temp = %d ",x,j,A[j],temp);
21                 x -= 2;
22             }
23         //    printf("i = %d\n",i);
24             ans = min(ans, temp);
25         }
26         printf("%d\n",ans);
27     }
28     return 0;
29 }