思路：链表

蒟蒻的第一篇题解，求通过。

题目大意：

有

n

个人，排成一列，进行

k

次操作，每次将中间的人移到左边或右边，并改变下一次操作的方向。

思路：

阅读题面，我们不难想到用数组模拟。
但是数组的删除操作太费时，会 TLE。
数组删除操作太耗时，我们就用删除操作时间复杂度为 $O(1)$ 的链表。
不知道链表的戳这里。
还有一个问题：

k

太大也会超时。
打表不难发现，每进行

2n

次，链表恢复初始值。
所以，我们完全可以用

k \bmod 2n

代替

k

。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
list<int>q;//链表
int main() {
	int T;
	cin>>T;
	while(T--) {
		long long n,x,k;//不开long long见祖宗
		cin>>n>>x>>k;
		k%=n*2;//一定要有
		for(int i=1; i<=n; i++)q.push_back(i);//初始化
		for(int i=1; i<=k; i++) {
			if(x==0) {
				auto it = q.begin();//迭代器
				advance(it, n/2);
				q.push_front(*it);
				q.erase(it); //删除
			}
			if(x==1) {
				auto it = q.begin();
				advance(it, n/2);
				q.push_back(*it);
				q.erase(it);
			}
			x=1-x;
		}
		for (const auto& elem : q) {  //遍历输出
			std::cout << elem << " ";
		}
		cout<<"\n";
		q.clear();
	}
	return 0;
}

这时，我们会发现一个严重的问题：TLE。
分析一下代码，我们发现：迭代器的移动时间复杂度为

O(n)

。
怎么办呢？干脆就不让它移动了。
我们可以建两个链表，一个模拟左边，一个模拟右边，一个装

n \div 2

个数，一个装

n \div 2 + 1

个数。
每次操作，拿出操作方向反方向的链表最靠近中间的数（左链表的尾，右链表的头）进行操作。操作后操作方向的比另一个多一个数。

AC代码：

CPP

#include<bits/stdc++.h>
using namespace std;
list<int>q1;//左链表和右链表
list<int>q2;
int main() {
	int T;
	cin>>T;
	while(T--) {
		long long n,x,k;
		cin>>n>>x>>k;
		k%=n*2;
		int mid=(n+1)/2;
		if(x==1) {//初始化分两种情况
			for(int i=1; i<=mid; i++) q1.push_back(i);
			for(int i=mid+1; i<=n; i++) q2.push_back(i);
		} else {
			for(int i=1; i<mid; i++) q1.push_back(i);
			for(int i=mid; i<=n; i++) q2.push_back(i);
		}

		for(int i=1; i<=k; i++) {
			if(x==0) {//操作
				q1.push_front(q2.front());
				q2.pop_front();
			}
			if(x==1) {
				q2.push_back(q1.back());
				q1.pop_back();
			}
			x=1-x;//改操作方向
		}
		for (const auto& elem : q1) {//遍历输出
			cout << elem << " ";
		}
		for (const auto& elem : q2) {
			cout << elem << " ";
		}
		cout<<"\n";
		q1.clear();//多测记得清空
		q2.clear();
	}

	return 0;
}

题解：P11463 N角进攻

文章操作

思路：链表

题目大意：

思路：

代码：

AC代码：

相关推荐

评论

题解：P11463 N角进攻