E. Yet Another Division Into Teams

代码:

// Created by CAD on 2019/11/6.
#include <bits/stdc++.h>

#define fi first
#define se second
#define pii pair<long long,int>
using namespace std;

const int maxn=2e5+5;
pii a[maxn];
int pre[maxn];
int out[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;  cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i].fi,a[i].se=i;
    sort(a+1,a+n+1);
    pii sum={0,0},t1={0,0},t2={0,0};
    for(int i=4;i<=n;++i)
    {
        pre[i]=sum.se;
        pii temp={sum.fi+a[i].fi-a[i-1].fi, i};
        sum=max(sum,t1);
        t1=t2,t2=temp;
    }
    cout<<a[n].fi-a[1].fi-sum.fi<<" ";
    int i=sum.se;
    int v=n,cnt=0;
    while(v>0)
    {
        int u=i;
        cnt++;
        for(;u<=v;u++)
            out[a[u].se]=cnt;
        v=i-1,i=pre[i];
    }
    cout<<cnt<<endl;
    for(i=1;i<n;++i)
        cout<<out[i]<<" ";
    cout<<out[n]<<endl;
    return 0;
}
01-03 00:44