题意

n个人，每人有一个能力值a[i]，要求分成多个队伍，每个队伍至少3个人，使得所有队伍的max(a[i])-min(a[i])之和最小。

分析

不会巧妙的dp，想了一天只想到了暴力的dp。
先排序，设\(dp[i]\)表示到前i个数组队，所有队伍的最小极差和。
转移方程为\(dp[i]=min(dp[j-1]+a[i]-a[j])\)for j in 1...i-2。即\(dp[i]=a[i]+min(dp[j-1]-a[j])\)。
所以可以枚举i，然后用优先队列维护\(dp[j-1]-a[j]\)，注意j最大是i-2。
为了方便最后输出方案，再维护一个len数组，表示前i个人当前i所在队伍的人数，最后从后往前递推，每次\(i-=len[i]-1\)，就能标记队伍的分割点，然后类似差分的思想扫一遍即可得到答案。
还有10天就退役了，退役前不会dp，希望退役后能学会dp吧。
突然想到好像可以不用优先队列了，反正只要往一个方向扫同时维护一个最小值就可以了。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+50;

typedef long long ll;

int n;

pair<ll,int> a[N];

ll dp[N];

int ans[N],vis[N],len[N];

queue<int> tmp;

struct node{

    ll dp;

    int i;

    bool operator<(const node& rhs)const{

        return dp>rhs.dp;

    }

};

priority_queue<node> q;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%lld",&a[i].first);

        a[i].second=i;

    }

    sort(a+1,a+1+n);

    dp[3]=a[3].first-a[1].first;

    len[3]=3;

    if(n>=4){

        dp[4]=a[4].first-a[1].first;

        len[4]=4;

        tmp.push(4);

    }

    if(n>=5){

        dp[5]=a[5].first-a[1].first;

        len[5]=5;

        tmp.push(5);

    }

    for(int i=6;i<=n;i++){

        int t=tmp.front();

        q.push(node{dp[t-1]-a[t].first,t});

        tmp.pop();

        auto mn=q.top();

        dp[i]=a[i].first+mn.dp;

        len[i]=i-mn.i+1;

        tmp.push(i);

    }

    int team=0;

    for(int i=n;i>=1;i--){

        vis[i]=++team;

        i-=len[i]-1;

    }

    int c=0;

    for(int i=n;i>=1;i--){

        if(vis[i]){

            c=vis[i];

        }

        ans[a[i].second]=c;

    }

    printf("%lld %d\n",dp[n],team);

    for(int i=1;i<=n;i++){

        printf("%d%c",ans[i],i==n?'\n':' ');

    }

    return 0;

}

巴特西

Codeforces1256E_Yet Another Division Into Teams

题意

分析

代码

最新文章

热门文章