跑步训练

NC220678. 跑步训练

描述

有 $\mathit n$ 个人正在操场上排成一列慢跑以进行跑步训练，从最靠前的人编号 $\text 1,2,...,n$ 。

可是队伍里有人觉得跑的太慢了，经常会跑出队伍。而且这个人会带着他后面的 $x$ 个人一起跑出，他们会快跑到队伍的最前头并保持他们的相对顺序不变。

请你输出在最后一次跑出结束后，队伍从头到尾的人员编号。

输入描述

第一行两个以空格分隔的整数。第一个表示队伍人数，第二个表示接下来会有次跑出。
接下来会有行，表示每一次跑出的信息。每一行的第一个整数表示这一次跑出的人的编号，第二个整数表示这一次他后面和他一起跑的人数有个。

输出描述

一行个以空格分隔的整数依次代表队伍从头到尾的人员编号。

示例1

输入:

5 2
2 4
3 1

输出:

3 4 2 5 1

说明:

初始时队伍有5个人，接下来会有2次跑出。队伍初始的时候状态为：

1 2 3 4 5
第一次跑出，编号2带着他后面的4个人（其实没有4个，只有3个）跑到最前面，则队伍变成：
2 3 4 5 1
第二次跑出，编号3带着他后面的1个人（也就是4）跑到最前面，则队伍变成：

3 4 2 5 1

示例2

输入:

输出:

2 3 4 5 1

说明:

第二次跑出结果如示例一所述，第三次跑出，只有编号2，他后面没有人，因此队伍变成：

2 3 4 5 1

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 55ms, 内存消耗: 1744K, 提交时间: 2021-05-08 16:58:58

#include<iostream>
using namespace std;
int n,q,i,j,x,y,head,pre[1000000],nxt[1000000];
int main(){
	scanf("%d%d\n",&n,&q);
	head=1;
	for (i=1;i<n;i++) nxt[i]=i+1;
	for (i=2;i<=n;i++) pre[i]=i-1;
	for (;q--;){
		scanf("%d%d\n",&x,&y);
		if (x==head) continue;
		for (i=x;y>0 && nxt[i];y--) i=nxt[i];
		if (pre[x]) nxt[pre[x]]=nxt[i];
		if (nxt[i]) pre[nxt[i]]=pre[x];
		pre[head]=i;
		nxt[i]=head;
		head=x;
		pre[x]=0;
	}
	for (i=head,j=1;j<=n;j++,i=nxt[i]) printf("%d ",i);
}

上一题

下一题

详情