题解：P11463 N角进攻

Nahida_Official · 2024-12-26 15:38:01 · 题解

题目传送门

通过描述和所给例子不难发现，当队列中有 n 个队员时，无论开始状态是向左还是向右传，在经过 n 次传球后，队列会进行反转。

举例如下：

输入：
7
7 0 1
7 0 2
7 0 3
7 0 4
7 0 5
7 0 6
7 0 7
输出：
4 1 2 3 5 6 7 
4 1 2 5 6 7 3 
5 4 1 2 6 7 3 
5 4 1 6 7 3 2 
6 5 4 1 7 3 2 
6 5 4 7 3 2 1 
7 6 5 4 3 2 1

输入:
7
7 1 1
7 1 2
7 1 3
7 1 4
7 1 5
7 1 6
7 1 7
输出：
1 2 3 5 6 7 4 
5 1 2 3 6 7 4 
5 1 2 6 7 4 3 
6 5 1 2 7 4 3 
6 5 1 7 4 3 2 
7 6 5 1 4 3 2 
7 6 5 4 3 2 1 

所以在经过 2 \times n 次传球后，队列就会回到初始状态。

由此可以想到将操作次数 k \bmod 2 \times n 之后进行模拟。

思路 1：

建立一个数组模拟操作，每次操作之后对数组进行更新，但由于更新数组需要双层循环，在题目条件 3 \le n \le 2\times 10^5 限制下会 TLE。

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int MANX=1e6;
ll T,n,x,k,mid;
int a[MANX];
void change(){
    if(x==0){
        int y=a[mid];
        a[0]=y;
        for(int i=mid-1;i>=0;i--){
            a[i+1]=a[i];
        }
        x=1;
    }else if(x==1){
        int z=a[mid];
        a[n+1]=z;
        for(int i=mid;i<=n+1;i++){
            a[i]=a[i+1];
        }
        x=0;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        cin>>n>>x>>k;
        k%=2*n;
        for(int i=1;i<=n;i++){
            a[i]=i;
        }
        mid=(1+n)/2;
        for(int i=1;i<=k;i++){
            change();
        }
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }
        cout<<'\n';
    }
    return 0;
}

Record

既然数组暴力不可取，那么转换思路。

思路 2：

开两个双端队列，分别记录中间队员的左边和右边，而中间队员新建一个变量 mid 存储。

根据题目样例解释：

第 0 次传球后 : 1 2 3 （接下来 2 号球员向左传球）
第 1 次传球后 : 2 1 3 （接下来 1 号球员向右传球）
第 2 次传球后 : 2 3 1 （接下来 3 号球员向左传球）
第 3 次传球后 : 3 2 1

不难发现，当中间队员向左传球时，将中间队员压入左边队列的头部，并且将中间队员 mid 设置为左边队列的尾部并弹出；而向右方传球则将中间队员压入右边队列的尾部，并且将中间队员 mid 设置为右边队列的头部并弹出。

对队列操作不需要额外循环，单层循环即可。

另外需要注意的点：

• 记得转移状态（更新 x）。

• 在读入数据的时候记得两个队列都要从尾部压入数据，否则会导致原队列乱序而得不出正确答案。

• 别忘记输出 mid。

• 记得开 long long。

  Code：

  
  #include<bits/stdc++.h>
  #define ll long long
  using namespace std;
  const int MANX=1e6;
  ll T,n,x,k,num;
  deque<ll> a,b;
  ll mid;
  void change(){
  if(x==0){
      a.push_front(mid);
      mid=a.back();
      a.pop_back();
      x=1;
  }
  else if(x==1){
      b.push_back(mid);
      mid=b.front();
      b.pop_front();
      x=0;
  }
  }//模拟 
  void print(){
  for(int i=1;i<=num;i++){
      cout<<a.front()<<" ";
      a.pop_front();
  }
  cout<<mid<<" ";
  for(int i=1;i<=num;i++){
      cout<<b.front()<<" ";
      b.pop_front();
  }
  cout<<"\n";
  }
  int main(){
  ios::sync_with_stdio(false);
  //freopen("2.in","r",stdin);
  //freopen("2.out","w",stdout);
  cin>>T;
  while(T--){
      cin>>n>>x>>k;
      k%=(2*n);//取模 
      num=(n+1)/2-1;//左右队列的长度 
      for(int i=1;i<=num;i++){
          a.push_back(i);
      }
      mid=(n+1)/2;
      for(int i=mid+1;i<=n;i++){
          b.push_back(i);
      }
      for(int i=1;i<=k;i++){
          change();
      }
      print();
  }
  return 0;
  }

 [AC Record](https://www.luogu.com.cn/record/196103636)