题解：AT_arc198_c [ARC198C] Error Swap

· · 题解

首先，发现操作不改变序列总和，\sum a_i\neq \sum b_i 显然无解。设 c_i=a_i-b_i。

考虑对于 1\leq x<y<z\leq n 的三元组 (a_x,a_y,a_z) 以及如下四种操作：

  1. (a_x,a_y,a_z)\rightarrow(a_y-1,a_x+1,a_z)\rightarrow(a_y-1,a_z-1,a_x+2)\rightarrow(a_x+1,a_z-1,a_y)\rightarrow(a_x+1,a_y-1,a_z)
  2. (a_x,a_y,a_z)\rightarrow(a_x,a_z-1,a_y+1)\rightarrow(a_z-2,a_x+1,a_y+1)\rightarrow(a_y,a_x+1,a_z+1)\rightarrow(a_x,a_y-1,a_z+1)
  3. (a_x,a_y,a_z)\rightarrow(a_z-1,a_y,a_x+1)\rightarrow(a_z-1,a_x,a_y+1)\rightarrow(a_x-1,a_z,a_y+1)\rightarrow(a_x-1,a_y,a_z+1)
  4. (a_x,a_y,a_z)\rightarrow(a_z-1,a_y,a_x+1)\rightarrow(a_y-1,a_z,a_x+1)\rightarrow(a_x,a_z,a_y)\rightarrow(a_x,a_y-1,a_z+1)

由这四种操作，我们可以在 4 次操作内完成将一个 c_i>0 的位置 -1 并且将一个 c_j<0 的位置 +1。

注意特判 n=2 和三元组的存在性情况。多出来的额外次数可以用来处理三元组。

#include<iostream>
#include<algorithm>
#include<numeric>
#include<vector>
const int sz=110;
int A[sz],B[sz];
std::vector<std::pair<int,int>>ans;
void adda(int a,int b,int c){
  ans.emplace_back(a,b);
  ans.emplace_back(b,c);
  ans.emplace_back(a,c);
  ans.emplace_back(b,c);
  A[a]++,A[b]--;
}
void addb(int a,int b,int c){
  ans.emplace_back(b,c);
  ans.emplace_back(a,b);
  ans.emplace_back(a,c);
  ans.emplace_back(a,b);
  A[b]++,A[c]--;
}
void suba(int a,int b,int c){
  ans.emplace_back(a,c);
  ans.emplace_back(b,c);
  ans.emplace_back(a,b);
  ans.emplace_back(b,c);
  A[a]--,A[c]++;
}
void subb(int a,int b,int c){
  ans.emplace_back(a,c);
  ans.emplace_back(a,b);
  ans.emplace_back(a,c);
  ans.emplace_back(b,c);
  A[b]--,A[c]++;
}
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin>>n;
  for(int i=1;i<=n;i++)std::cin>>A[i];
  for(int i=1;i<=n;i++)std::cin>>B[i];
  if(std::accumulate(A+1,A+n+1,0)!=std::accumulate(B+1,B+n+1,0))std::cout<<"No\n",exit(0);
  if(n==2){
    if(A[1]==B[1])std::cout<<"Yes\n0\n";
    else if(A[1]==B[2]-1)std::cout<<"Yes\n1\n1 2\n";
    else std::cout<<"No\n";
    return 0;
  }
  for(int i=1,j=2,k=1;i<n;i++){
    while(A[i]>B[i]){
      while(j<n&&A[j]>=B[j])j++;
      if(i==1&&j==2)j++;
      while(j<n&&A[j]>=B[j])j++;
      if(i!=1&&j==i+1)subb(i-1,i,j);
      else suba(i,i+1,j);
    }
    while(A[i]<B[i]){
      while(k<n&&A[k]<=B[k])k++;
      if(i!=1&&k==n)addb(i-1,i,k);
      else if(i==1&&k==n)adda(i,i+1,k);
      else adda(i,k,k+1);
    }
  }
  std::cout<<"Yes\n"<<ans.size()<<"\n";
  for(auto [x,y]:ans)std::cout<<x<<" "<<y<<"\n";
  return 0;
}