题解 P4699 【[CEOI2011]Teams】

· · 题解

这题网上好像找不到比较详细的题解

先解决第一问，如何求出最大队伍数

我们先按a_{i}从小到大排序一趟，显然，如果a_{i+1}满足那么a_{i}也必定满足。手玩几组数据易得，每组人员都是连接在一起的，即：a_{i},a_{i+1},a_{i+2},\ldots

我们开两个数组来记录：

$f_{i}$ : 第$i$个人为一组的结尾最多分几组 转移方程非常简洁，即： $f_{i} = Max_{i-a_{i}}+1

当然前提必须保证： i>=a_{i} 且 Max_{i-a_{i}}>=0（或者说Max_{i-a_{i}}已经被更新过了）

再考虑如何更新Max_{i}

根据定义，Max_{i} 表示前i个人最多分几组，所以 :

Max_{i}=max(f_{i},Max_{i-1})

初值: Max_{0}=0

第一问做出来后第二问就容易了 看到“**最小化人数最多**的队伍的人数”，自然而然就会想到用二分来枚举答案 $mid$：人数最多的队伍人数 再开一个数组： $Lst_{i}$： 枚举完第 $i$ 个人时上一组的结尾位置（思考 因为$mid$表示人数最多的队伍人数，所以: $i-Lst_{i-a_{i}}<=mid

同时更新操作也和Max数组类似：

当f_{i}>=Max_{i-1}时：Lst_{i}=i （新开一组，自己为结尾位置）

否则： Lst_{i}=Lst_{i-1} （因为没有新开一组，上一组结尾位置即不变）

在满足组数最多的情况下，用二分来查找 mid 的最小值，即为答案

详见代码：

#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n,Ans,Min,Max[maxn],f[maxn],lst[maxn],L,R,mid;
struct lc{
    int x,id;
    bool operator <(const lc b)const{return x<b.x;}
}a[maxn];
inline int read(){
    int ret=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
inline int check(int len){
    memset(lst,0,sizeof lst);
    memset(f,-1,sizeof f);
    memset(Max,-1,sizeof Max);
    Max[0]=0;int inf=Max[1];
    for (int i=1;i<=n;i++){
        if (a[i].x<=i&&Max[i-a[i].x]>=0&&lst[i-a[i].x]+len>=i) f[i]=Max[i-a[i].x]+1;     //判断是否能新成一个组 
        if (f[i]>=Max[i-1]) lst[i]=i,Max[i]=f[i];
        else lst[i]=lst[i-1],Max[i]=Max[i-1];
    }
    return f[n];           //返回最大组数 
}
int main(){
    n=read();
    for (int i=1;i<=n;i++) a[i]=(lc){read(),i};
    sort(a+1,a+n+1); 
    printf("%d\n",Min=check(n));     //记录最大组数 
    L=0,Ans=R=n;
    while (L<=R){
        mid=L+R>>1;
        if (check(mid)==Min) Ans=mid,R=mid-1;       //查找满足最大组数的前提下mid最小为多少 
        else L=mid+1;
    }
    check(Ans),R=n;       //最后要在check一遍来计算lst数组 
    while (R){  
        L=lst[R-a[R].x];
        printf("%d",R-L);
        for (int i=L+1;i<=R;i++) printf(" %d",a[i].id); //输出答案 
        putchar('\n');R=L;
    }
    return 0;
}

可能讲的不够详细，如有不懂的地方欢迎评论区留言或者私信