题目链接:https://codeforces.com/contest/1256/problem/E
题目大意:有n个人,每个人有一个能力,现在让你分组。每组至少3个人。团队的多样性是这个团队的:最大能力-最小能力。
总的多样性:所有团队的多样性的和。

让你分组:使总多样性最小。

我们尽量让能力相近的人分到一组。
我们先排个序,就会得到一个贪心的策略:每个组最多为连续的5个人。如果6个人,分成两组一定更优。

dp[i]:前i个人的最小总的多样性。

dp[i]=dp[j]+a[j]-a[i] (i-3-1<=j<=i-3+1)

代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct node{
    int i;
    int x;
}a[200005];
LL f[200005];
int vis[200005];
int p[200005];
int cmp(node &a, node &b){
    return a.x>b.x;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        f[i]=(1ll<<60);
        scanf("%d", &a[i].x);
        a[i].i=i;
    }
    sort(a+1, a+n+1, cmp);
    f[0]=0;
    for(int i=3; i<=n; i++){
        if(i-3+1>=1&&f[i]>f[i-3]+a[i-3+1].x-a[i].x){
            f[i]=f[i-3]+a[i-3+1].x-a[i].x;
            p[i]=i-3;
        }
        if(i-3>=1&&f[i]>f[i-3-1]+a[i-3].x-a[i].x){
            f[i]=f[i-3-1]+a[i-3].x-a[i].x;
            p[i]=i-3-1;
        }
        if(i-3-1>=1&&f[i]>f[i-3-2]+a[i-3-1].x-a[i].x){
            f[i]=f[i-3-2]+a[i-3-1].x-a[i].x;
            p[i]=i-3-2;
        }
    }
    printf("%lld ", f[n]);
    int L=p[n], R=n, tot=1;
    while(R){
        while(R>L){
            vis[a[R].i]=tot;
            R--;
        }
        R=L, L=p[R], tot++;
    }
    printf("%d\n", tot-1);
    for(int i=1; i<=n; i++){
        printf("%d ", vis[i]);
    }
    printf("\n");

    return 0;
}