题解：P11463 N角进攻

luoguzbh0011 · 2025-05-11 09:45:53 · 题解

思路：链表

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

题目大意：

有 n 个人，排成一列，进行 k 次操作，每次将中间的人移到左边或右边，并改变下一次操作的方向。

思路：

阅读题面，我们不难想到用数组模拟。
但是数组的删除操作太费时，会 TLE。
数组删除操作太耗时，我们就用删除操作时间复杂度为 O(1) 的链表。
不知道链表的戳这里。
还有一个问题：k 太大也会超时。
打表不难发现，每进行 2n 次，链表恢复初始值。
所以，我们完全可以用 k \bmod 2n 代替 k。

代码：

#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代码：

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