第五届华中区程序设计邀请赛暨武汉大学第十四届校赛网络预选赛 A

Problem 1603 - Minimum Sum

Time Limit: 2000MS Memory Limit: 65536KB
Total Submit: 564 Accepted: 157 Special Judge: No

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

题意：长度为n的数组A 任意取取出的数量为m 然后求所有 abs( A[B[i]]-A[B[j]] i<j ) 的和

题解：比赛的时候有一个思路题目时间限制是2000ms 但woj 测评 2000+ms 过了

先sort排序取连续的长度为m的序列re[] 求其sum值

预处理求 re[1]-re[2] =ans[2] 并记录前缀和

re[1]-re[3] =ans[3]

...

re[1]-re[m]=ans[m]

re[2]-re[3]=(re[1]-re[3])-(re[1]-re[2]) //

re[2]-re[4]=(re[1]-re[4])-(re[1]-re[2]) //将要求的量转化为已知量

 1 #include<iostream>
 2  #include<cstdio>
 3  #include<cmath>
 4  #include<algorithm>
 5  #include<cstring>
 6  using namespace std;
 7 int n,m;
 8 struct node
 9  {
10      long long  w;
11      int pos;
12  }N[100005];
13 long long ans[100005];
14 long long  re[100005];
15 long long  summ[100005];
16 long long qq;
17 long long exm;
18 long long gg;
19 int l=0,r=0;
20 bool cmp1(struct node aa,struct node bb)
21  {
22      if(aa.w<bb.w)
23      return true;
24      return false;
25  }
26 long long fun( int ll,int rr)
27  { 
28        l=ll;
29        r=rr;
30        int jishu=1;
31        for(int i=l;i<=r;i++)
32            re[jishu++]=N[i].w;
33            exm=0;
34            summ[1]=0;
35            ans[1]=0;
36          for(int i=2;i<jishu;i++)
37            { 
38              ans[i]=abs(re[1]-re[i]);
39              exm+=ans[i];
40              summ[i]=exm;
41            }
42            qq=0;
43          for(int i=1;i<jishu;i++)
44          {
45              qq=qq+summ[jishu-1]-summ[i];
46              qq=qq-ans[i]*(jishu-i-1);
47          }
48      return qq;
49  }
50 int main()
51  {
52      while(scanf("%d %d",&n,&m)!=EOF)
53      {
54          memset(N,0,sizeof(N));
55          for(int i=1;i<=n;i++)
56          {
57            scanf("%lld",&N[i].w);
58            N[i].pos=i;
59          }
60          sort(N+1,N+1+n,cmp1);
61          gg=fun(1,m); 
62          for(int i=2;i<=n-m+1;i++)
63          {
64              gg=min(gg,fun(i,i+m-1));  
65          }
66            printf("%lld
",gg);    
67      }
68      
69  }

第五届华中区程序设计邀请赛暨武汉大学第十四届校赛 网络预选赛 A

第五届华中区程序设计邀请赛暨武汉大学第十四届校赛网络预选赛 A