「51nod 1510」最小化序列

发表于

现在有一个长度为 nn 的数组 AA ，另外还有一个整数 kk 。数组下标从 11 开始。

现在你需要把数组的顺序重新排列一下使得下面这个的式子的值尽可能小。

∑i=1n−k∣A[i]−A[i+k]∣\sum_{i=1}^{n-k}{|A[i]-A[i+k]|}

特别的，你也可以不对数组进行重新排列。

Constraints

$ 2\leq n\leq 3\cdot 10^5$ ， 1≤k≤min(5000,n−1)1 \leq k \leq min(5000,n-1)

Solution

观察可得式子实际上将 nn 个数字分成了不相关的 kk 组，其中有 nmodkn \bmod k 组大小为 nk+1\frac{n}{k}+1 ，剩余的长度为 nk\frac{n}{k} 。

将 AA 数组排序后，贪心地得出每一组都是连续的一段，代价为最后一个数 −- 第一个数。

令 f(i,j)f(i,j) 表示当前已有 ii 组较大的分组与 jj 组较小的分组的最小代价，直接 dp 即可。

时间复杂度 O(k2)O(k^2) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=3e5+5;
const int K=5e3+5;
int lcnt,scnt,leng,seng;
int n,k,t,a[N],f[K][K];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void update(int &a,int b)
{
	if(a==-1)a=b;
	else a=min(a,b);
}
int main()
{
	n=read();k=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+n+1);
	lcnt=n%k;scnt=k-lcnt;
	leng=n/k+1;seng=n/k;
	memset(f,-1,sizeof(f));
	f[0][0]=0;
	for(int i=0;i<=lcnt;i++)
		for(int j=0;j<=scnt;j++)
		{
			if(f[i][j]==-1)continue;
			t=i*leng+j*seng;
			if(i!=lcnt)update(f[i+1][j],f[i][j]+a[t+leng]-a[t+1]);
			if(j!=scnt)update(f[i][j+1],f[i][j]+a[t+seng]-a[t+1]);
		}
	printf("%d",f[lcnt][scnt]);
	return 0;
}