自动搬运

查看原文

来自洛谷，原作者为

	xiaozeyu 这个家伙超级懒，什么也没有留下

搬运于2025-08-24 21:44:57，当前版本为作者最后更新于2019-10-26 13:20:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

既然不好写就换一个思路

这道题如果按每一小块直接算，既麻烦又费时，所以我们可以转换一下思路

我们可以把所有的数据接到一起，用一个算前缀和的数组进行标号，在每一次循环有效的处理每一组数据

#include<bits/stdc++.h>
using namespace std;
int n,g,sum[2050],t[2050],a[250005],ans=1;
bool f[250005];//定义
int main()
{
	f[1]=1;
	scanf("%d%d",&n,&g);
	for(int i=1;i<=g;i++)
	{
		scanf("%d",&t[i]);//输入每组大小
		sum[i]=sum[i-1]+t[i];//记录总数
		for(int j=sum[i-1]+1;j<=sum[i];j++)
			scanf("%d",&a[j]);//在每一小段输入每个
	}
	while(1)//多次循环一直找
	{
		int k=ans;//继承上一次循环结果
		for(int i=1;i<=g;i++)
		{
			int q,s=0;//清零
			for(int j=sum[i-1]+1;j<=sum[i];j++)//枚举每一段
			{
				if(f[a[j]])//是否参加
					s++;
				else 
					q=a[j];//标记
			}	
			if(t[i]-s==1)//至少k-1个奶牛参加派对时，必须邀请最后的一头奶牛
			{
				f[q]=1;//参加
				ans++;//总数加上这个
			}
		}
		if(k==ans)//两次循环结果不再变化，则已最优
		{
			cout<<ans;//输出
			return 0;
		}
	}
}