E. Yet Another Division Into Teams

Codeforces Round #598 (Div. 3)

思路

首先我们可以确定是选择的team长度最长为5，因为如果是6的话我们很可能有更优的选择权，而且当我们倒着弄(i->i+2quad i->i+3quad i->i+4)是可以遍历每一种可能的。

在遍历的过程中我们在(minn)数组中存了每个团队的上界和下界，比如说(minn[i+3]=i)，那么就是(i->i+3)

便于我们后期给(ans)数组赋答案。

转移方程：

[dp[i+2]=dp[i-1]+node[i+2].v-node[i].v\ dp[i+3]=dp[i-1]+node[i+3].v-node[i].v\dp[i+4]=dp[i-1]+node[i+4].v-node[i].v ]

每次可能比上一次优就更新。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(case, x) cout << case << "  : " << x << endl
#define open freopen("ii.txt", "r", stdin)
#define close freopen("oo.txt", "w", stdout)
#define IO                       
    ios::sync_with_stdio(false); 
    cin.tie(0);                  
    cout.tie(0)
#define pb push_back
using namespace std;
// #define int long long
#define lson rt << 1
#define rson rt << 1 | 1
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> PII;
const int maxn = 2e5 + 10;

int dp[maxn],ans[maxn],minn[maxn];
struct node{
    int v,pos;
    bool operator<(const node x)const{
        return v<x.v;
    }
}node[maxn];

void solve() {
    int n;cin>>n;
    for(int i=1;i<=n;++i){
        cin>>node[i].v;
        node[i].pos=i;
    }
    sort(node+1,node+1+n);
    for(int i=1;i<=n;++i){
        dp[i]=1e9;
    }

    for(int i=1;i<=n;++i){
        if(i+3<=n+1){
            if(dp[i+2]>=dp[i-1]+node[i+2].v-node[i].v)
                dp[i+2]=dp[i-1]+node[i+2].v-node[i].v,minn[i+2]=i;
        }
        if(i+4<=n+1){
            if(dp[i+3]>=dp[i-1]+node[i+3].v-node[i].v)
                dp[i+3]=dp[i-1]+node[i+3].v-node[i].v,minn[i+3]=i;
        }
        if(i+5<=n+1){
            if(dp[i+4]>=dp[i-1]+node[i+4].v-node[i].v)
                dp[i+4]=dp[i-1]+node[i+4].v-node[i].v,minn[i+4]=i;
        }
    }
//    for(int i=1;i<=n;++i){
//        debug(i,dp[i]);
//    }
    int tot=0;
    int now=n;
    while(now!=0){
        ++tot;
        for(int i=now;i>=minn[now];--i)
            ans[node[i].pos]=tot;
        now=minn[now]-1;
    }
    cout<<dp[n]<<' '<<tot<<endl;
    for(int i=1;i<=n;++i){
        cout<<ans[i]<<' ';
    }

}

int main() {
//    int t;
//    cin >> t;
//    while(t--) {
        solve();
//    }
}