CF571B-题解

CF571B

题意

给定数组\(A\) 和值\(k\) ，你可以重排\(A\) 中的元素，使得\(\displaystyle\sum_{i=1}^{n-k} |A_i-A_{i+k}|\) 最小。输出最小值。

思路

\(A_i,A_{i+k}\) 就等同于在将 \(i\) 模 \(k\) 的意义上把 \(A\) 分为若干组
贪心的想要使 \(\displaystyle\sum_{i=1}^{n-k} |A_i-A_{i+k}|\) 最小就等同于让每组内的数字差异尽可能小，所以将原数组进行排序。
设 \(dp_{i,j}\) 为选上述第一种组别 \(i\) 次，选第二种组别 \(j\) 次的最小值，对于每个组数字，结果为末项减首项，得到转移方程

dp[i][j]=min(dp[i-1][j]+a[now]-a[now-len]);
dp[i][j]=min(dp[i][j-1]+a[now]-a[now-len+1]);

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int a[N];
int dp[5003][5003];
int n,k,ans;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    memset(dp,0x3f,sizeof(dp));
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    int len=n/k,tot1=n%k,tot2;
    tot2=(n-tot1)/len-tot1;
    dp[0][0]=0;
    for(int i=0;i<=tot1;i++)
        for(int j=0;j<=tot2;j++)
        {
            int k=len*(i+j)+i;
            if(i)dp[i][j]=min(dp[i][j],dp[i-1][j]+a[k]-a[k-len]);
            if(j)dp[i][j]=min(dp[i][j],dp[i][j-1]+a[k]-a[k-len+1]);
            // cout<<k<<" "<<dp[i][j-1]+a[k]-a[k-len+1]<<" "<<dp[i-1][j]+a[k]-a[k-len]<<"\n";
        }
    cout<<dp[tot1][tot2];
    return 0;
}