自动搬运

查看原文

来自洛谷，原作者为

	LlLlCc 背井离乡，忍辱负重

搬运于2025-08-24 22:02:43，当前版本为作者最后更新于2020-05-07 11:12:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

我们开两个数组来记录：

$Max_{i}$ : 前$i$个人最多分几组

$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$

$Ans=f_{n}$ （因为要满足每个小朋友，所以第$N$个小朋友必取，$Ans$为$f_{n}$而并非$Max_{n}$）

第一问做出来后第二问就容易了

看到“最小化人数最多的队伍的人数”，自然而然就会想到用二分来枚举答案

$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;
}

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