自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 21:15:00，当前版本为作者最后更新于2023-06-08 20:04:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Source & Knowledge

2023 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

有 $n$ 张纸条，根据内容的连贯性被分为若干段，给出每张纸条在其连贯内容后的纸条编号，或给出下一段内容的开头纸条编号，或者说明已经没有更靠后的纸条。给出纸条按照时间顺序排序后的编号。

题目分析

本题考察数组的运用。

经过思考可以发现：除了时间最早的纸条，即排好序后的第一张纸条以外，所有的纸条都会出现在某一张纸条的后方，也就都会被提及——如果一张处于一段连贯内容的开头，就会在前一张纸条的输入部分被提及，否则，就会在连贯内容的前面的纸条中被提及。而第一张纸条在一段连贯内容的开头，但前面已经没有纸条了，所以不会被提及。所以，可以建立一个 $vis$ 数组判断每张纸条是否出现在输入部分中。只会有一张纸条不会出现，那张纸条就是开头。这里要注意，由于输入可能会有 -1 直接访问会因数组越界导致 RE，要特殊判断。

知道了开头就好办了。我们对每一张纸条开一个数组，从开头的纸条开始，先把它的连贯内容之后的纸条依次输出，然后，通过连贯内容最后一张纸条得到下一段连贯内容的开头，再把之后的输出……以此类推，直到发现了结束标志 -1，输出就停止。

数组的存储方式有两种，一是开一个二维数组，这样空间开销有一点大，但也没有问题。第二种方法是使用 vector 存储，能够动态申请空间，且长度可以直接查询，非常方便。这里给出使用 vector 的核心代码：

vector<int>p[2010];
bool vis[2010];

for(int i=1;i<=n;i++){
	cin >> m;
	if(m)
	for(int j=1;j<=m;j++){
		int x;
		cin >> x;
		vis[x]=1;
		p[i].push_back(x);//vector的插入
	}
	else {
		int x=read();
		if(x>0)vis[x]=1;//注意防止数组越界
		p[i].push_back(x);
	}
}
int s;
for(int i=1;i<=n;i++)if(!vis[i])s=i;//寻找起点
while(1){
	if(s==-1)return 0;//遇到终点，程序结束
	int siz=p[s].size();//这个函数指的是p[s]中的元素个数
	cout <<s<<" ";
	if(p[s][siz-1]==-1)return 0;//s是终点，程序结束
	for(int i=0;i<siz;i++)cout <<p[s][i]<<" ";//依次输出，注意 vector 的下标从0开始
	s=p[p[s][siz-1]][0];//vector 的下标从 0 开始，故最后一个元素的下标为 siz-1
}

视频题解