【BZOJ2587】【CEOI2011】Teams

Author Avatar
q234rty 9月 23, 2017

动态规划+堆即可。

将 a_i 从大到小排序，容易发现每一个团队都是一个区间。

考虑暴力DP：设 f(i) 为前 i 个人最多分成的团队个数， g(i) 为前 i 个人分成 f(i) 个团队，最大的团队的最少成员数。

易得

f(i)=\max_{j+a_{j+1}\leq i} f(j)+1\\ g(i)=\min_{j+a_{j+1}\leq i,f(j)+1=f(i)} \max(g(j),i-j)

考虑用一个链表维护 i 处新增的决策点，计算好 j 后把其添加到 a_{j+1}+j 处的链表中。

注意到 g(j) 相对 i 为常数，而 i−j 单调递增，那么一个 j 随 i 的增加， \max(g(j),i-j) 应该先取 g(j) 再取 i-j 。

考虑再使用一个链表维护 i 处有哪些 j 满足 g(j)=i-j ，计算好 j 后把其添加到 g(j)+j 处的链表中。

对于 g(j)<i-j ，用一个堆维护 f(j) 的最大值及 f(j) 取最大时 g(j) 的最小值。

对于 g(j) \geq i-j ，直接记录 f(j) 的最大值及 f(j) 取最大时 j 的最大值即可。

时间复杂度 O(n \log n) 。

本题存在时间复杂度 O(n) 的做法，参见lych_cys的题解 。

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long ll;
const int MAXSIZE=30000020;
const int INF=0x3f3f3f3f;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("2587.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
int cnt[1000002],tmp[1000002],a[1000002],b[1000002],f[1000002],g[1000002],lst[1000002];
int nxt[1000002],first[1000002],nxt2[1000002],first2[1000002];
void add(int p,int v){
    nxt[v]=first[p];
    first[p]=v;
}
void add2(int p,int v){
    nxt2[v]=first2[p];
    first2[p]=v;
}
struct cmp{
    bool operator ()(const int &x,const int &y){
        return f[x]<f[y] || (f[x]==f[y] && g[x]>g[y]);
    }
};
typedef __gnu_pbds::priority_queue<int,cmp> heap;
heap q;
heap::point_iterator it[1000001];  
int main(){
    init();
    int n=readint();
    for(int i=1;i<=n;i++)
        tmp[i]=readint(),cnt[tmp[i]]++;
    for(int i=n;i;i--)
        cnt[i]+=cnt[i+1];
    for(int i=1;i<=n;i++)
        b[cnt[tmp[i]]]=i,a[cnt[tmp[i]]--]=tmp[i];
    int now=0;
    //for(int i=1;i<=n;i++)
        //printf("%d ",a[i]);
    for(int i=1;i<=n;i++){ //g[j]+j<=i
        //puts("WTF");
        for(int to=first2[i];to;to=nxt2[to]){
            if (g[to]+to<i){
                if (f[to]>=f[now])
                    now=to;
            }else {
                //printf("adding %d\n",to);
                it[to]=q.push(to);
            }
        }
        //puts("233");
        for(int j=first[i];j;j=nxt[j]){
            if (j+a[j+1]>i)
                continue;
            //printf("%d\n",j);
            q.erase(it[j]);
            if (f[j]>f[now] || (f[j]==f[now] && j>now))
                now=j;
        }
        //puts("tat");
        if (q.empty()){
            if (!now && i<a[1]){
                g[i]=INF;
                continue;
            }
            f[i]=f[now]+1;
            g[i]=i-now;
            lst[i]=now;
        }else{
            int x=q.top();
            if (f[x]==f[now]){
                f[i]=f[x]+1;
                if (i-now<g[x])
                    g[i]=i-now,lst[i]=now;
                else g[i]=g[x],lst[i]=x;
            }else if (f[x]<f[now])
                f[i]=f[now]+1,g[i]=i-now,lst[i]=now;
            else f[i]=f[x]+1,g[i]=g[x],lst[i]=x;
        }
        //puts("qwq");
        //printf("f[%d]=%d\n",i,f[i]);
        if (g[i]+i<=n)
            add(g[i]+i,i);
        if (i<n && i+a[i+1]<=n)
            add2(i+a[i+1],i);
    }
    printf("%d\n",f[n]);
    for(int i=n;i;){
        int w=lst[i];
        printf("%d ",i-w);
        while(i>w){
            printf("%d ",b[i]);
            i--;
        }
        putchar('\n');
    }
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2017/09/23/bzoj2587/

隐藏