ARC198C 题解

题目传送门

题意简述

有两个长度为 \(n\) 的序列 \(A\) 和 \(B\)。
定义换交操作为：

• 选择 \((i,j)\) 满足 \(1\le i<j\le n\)，将 \(A_{i}\) 替换为 \(A_{j}-1\)，将 \(A_{j}\) 替换为 \(A_{i}+1\)。

问能否在 \(31000\) 次换交操作内将 \(A\) 变成 \(B\)，若可行，并输出任意一种方案。

思路

首先，我们观察到 \(A_{i}+A_{j}=(A_{j}-1)+(A_{i}+1)\)。因此进行换交操作后，\(A\) 数组的和是不会发生改变的。
那么如果在最开始，\(A\) 数组的和不等于 \(B\) 数组的和，那么一定无解。

另外，我们发现，对于一个数 \(A_{i}\)，其往前交换几次，数字就会减少多少，而往后交换几次，数字就会增大多少。

对于这种将某种状态，变成另一种状态的构造题，常见的做法是定义一种中间状态 \(M\)，先将 \(A\) 变成 \(M\)，再将 \(M\) 变成 \(B\)。对于前者直接构造，对于后者，可以倒过来从 \(B\) 变成 \(M\)，再逆序输出操作即可。
那么这道题可以这么做吗？
答案是可行的，虽然题目要求中钦定了 \(i<j\)，但是我们来模拟一下。对于 \(a,b\) 这两个数，我们进行两次换交操作，依次可以得到 \(b-1,a+1\) 和 \(a,b\)。因此换交操作是可逆的，只要你保证每次操作的时候，\(i<j\) 即可。

对于中间状态，可以设置为例如 \(1,1,\dots,1,-(n-1)+\sum_{i=1}^{n}A_{i}\) 之类的。
但我的方法并不是这么做的，这里介绍一种不需要中间状态的做法。

正确的交换操作

首先，我们考虑一种简单得多的情况：将 \(A\) 和 \(B\) 从小到大排序后，\(A=B\)。 那么我们只需要枚举 \(B_{i}\)，去找到到匹配的 \(A_{j}\)，将 \(A_{j}\) 与 \(A_{i}\) 进行交换即可。这样的话，我们最多进行 \(n\) 次交换即可。
我们怎么使用换交操作，做到交换呢？

假设我们要将 \(A_{i}\) 和 \(A_{j}\) 两个数进行交换。假如只有这两个数，那么可以达到的状态只有 \(A_{j}-1,A_{i}+1\) 和 \(A_{i},A_{j}\) 两种，一般情况下，显然是没法完成交换的。因此我们引入一个临时的数 \(A_{k}\)。

因为钦定了换交操作时 \(i<j\)，所以我们分三种情况。

1. \(k<i<j\)：我们相当于要让 \(A_{i}\) 往前一次，再往后一次，最后到达 \(A_{j}\) 的位置。
   那么我们只需要先将 \(A_{k}\) 和 \(A_{i}\) 换交，得到 \(A_{i}-1,A_{k}+1,A_{j}\)。
   然后将 \(A_{i}-1\) 和 \(A_{j}\) 换交，得到 \(A_{j}-1,A_{k}+1,A_{i}\)。
   最后将 \(A_{j}-1\) 和 \(A_{k}+1\) 换交，即可得到 \(A_{k},A_{j},A_{i}\)。
   
2. \(i<j<k\)：类似上一种情况的分析，可行的步骤如下：
   将 \(A_{i}\) 和 \(A_{k}\) 换交，得到 \(A_{k}-1,A_{j},A_{i}+1\)。
   再将 \(A_{j}\) 和 \(A_{i}+1\) 换交，得到 \(A_{k}-1,A_{i},A_{j}+1\)。
   最后将 \(A_{k}-1\) 和 \(A_{j}+1\) 换交，即可得到 \(A_{j},A_{i},A_{k}\)。
   
3. \(i<k<j\)：这种情况很少会出现，当且仅当 \(i=1\) 且 \(j=n\) 是会出现。手玩一下可以发现不能像前两种方法一样处理。但是我们可以转化，不妨我们先交换 \(A_{k}\) 和 \(A_{j}\)，再交换 \(A_{i}\) 和 \(A_{j}\)，最后再交换 \(A_{i}\) 和 \(A_{k}\)，这样用 \(9\) 步实现了交换 \(A_{i}\) 和 \(A_{j}\)。
   实际上，在思考时，我发现了一种 \(5\) 步的方法，具体步骤如下：
   \(A_{i}\) 与 \(A_{j}\) 换交，得到 \(A_{j}-1,A_{k},A_{i}+1\)。
   \(A_{j}-1\) 与 \(A_{k}\) 换交，得到 \(A_{k}-1,A_{j},A_{i}+1\)。
   \(A_{j}\) 与 \(A_{i}+1\) 换交，得到 \(A_{k}-1,A_{i},A_{j}+1\)。
   \(A_{k}-1\) 与 \(A_{i}\) 换交，得到 \(A_{i}-1,A_{k},A_{j}+1\)。
   \(A_{i}-1\) 与 \(A_{j}+1\) 换交，得到 \(A_{j},A_{k},A_{i}\)。

根据前文，最多会出现 \(1\) 次第三种情况，因此对于开头的问题，最多可能的换交操作只会有 \(3n+2\) 次。
换句话说，我们可以在至多 \(3n+2\) 次换交操作下，将一个数组重新排列。

改变权值

我们不妨先将 \(A\) 和 \(B\) 从小到大排序，得到 \(A'\) 和 \(B'\)，根据前文，我们只需要将 \(A'\) 变成 \(B'\)，就完成了这道题目。
此时 \(A\) 中的数不一定全部等于 \(B\) 中的数，我们需要增加一些数的权值，降低一些数的权值。

我们现在有两个数 \(A_{i}\) 和 \(A_{j}\)，我们有两种操作：
操作一：将 \(A_{i}\) 变成 \(A_{i}-1\)，将 \(A_{j}\) 变成 \(A_{j}+1\)。
实现过程，我们先将 \(A_{i}\) 和 \(A_{j}\) 交换，然后再使用一次换交操作即可。
操作二：将 \(A_{i}\) 变成 \(A_{i}+1\)，将 \(A_{j}\) 变成 \(A_{j}-1\)。
实现过程：我们先将 \(A_{i}\) 和 \(A_{j}\) 换交，得到 \(A_{j}-1\) 和 \(A_{i}+1\)，然后再交换即可。

这样，我们在不改变原数的顺序的情况下，完成了改变权值的操作。

实际上，我们也可以通过不断将某个数往前挪和往后挪来实现这一个数的加和减，这也是一种正确的方法，可以尝试自行思考一下。

正解

根据前文的判断，此时一定有 \(\sum_{i=1}^{n}A_{i}=\sum_{i=1}^{n}B_{i}\)。并且需要降低的权值的和是等于需要增加的权值的，并且我们现在是两个有序的数组，那么我们不妨使用双指针来实现。
假如 \(A'_{l}>B'_{l}\) 或者 \(A'_{r}<B'_{r}\)，那么我们用前面的操作一。
假如 \(A'_{l}<B'_{l}\) 或者 \(A'_{r}>B'_{r}\)，那么我们用前面的操作二。
假如 \(A'_{l}=B'_{l}\)，那么我们将 \(l\) 往右挪动。
假如 \(A'_{r}=B'_{r}\)，那么我们将 \(r\) 往左挪动。
当 \(l=r\) 的时候，我们便完成了任务。

我们来计算一下所需的换交次数。
首先是从 \(A\) 变成 \(A'\) 以及从 \(B'\) 变成 \(B\)，这个需要至多 \(6n+4\) 次操作。
接下来是从 \(A'\) 变成 \(B'\)。因为和相等，两个数组均有序，双指针使得我们相当于是两边一起处理，所以可能的最大需要调整次数为 \(\dfrac{n}{2}V\)，所需的换交次数至多为 \(4\times\dfrac{n}{2}V+2V=2nV+2V\)。
两者加一起得到 \(2nV+2V+6n+4\)，因为 \(n\) 和 \(V\) 同阶，所以也就是 \(2n^2+8n+4\)，最大也就是当 \(n=100\) 时，值为 \(20804\)，轻松通过。

一处细节

发现我们前面的所有操作都基于存在一个临时的位置 \(k\)，那么当 \(n=2\) 时，上述方法都不管用。
但是因为在同一对 \((i,j)\) 进行两次换交操作会恢复原样，所以 \(n=2\) 时只会有 \(A_{1},A_{2}\) 和 \(A_{2}-1,A_{1}+1\) 两种情况。直接和 \(B\) 比较一下即可。

代码

// Problem: C - Error Swap
// Contest: AtCoder - AtCoder Regular Contest 198 (Div. 2)
// URL: https://atcoder.jp/contests/arc198/tasks/arc198_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,a[MAXN],b[MAXN],A[MAXN],B[MAXN],suma,sumb;
vector<pair<int,int> > ans;

//z x y
//x-1 z+1 y
//y-1 z+1 x
//z y x

//x z y
//y-1 z x+1
//z-1 y x+1
//z-1 x y+1
//x-1 z y+1
//y z x

//x y z
//z-1 y x+1
//z-1 x y+1
//y x z

void swap(int x,int y,int z){
    if(z<x){
        ans.push_back(make_pair(x,z));
        ans.push_back(make_pair(z,y));
        ans.push_back(make_pair(x,z));
    }
    else if(z<y){
        ans.push_back(make_pair(x,y));
        ans.push_back(make_pair(x,z));
        ans.push_back(make_pair(z,y));
        ans.push_back(make_pair(x,z));
        ans.push_back(make_pair(x,y));
    }
    else{
        ans.push_back(make_pair(x,z));
        ans.push_back(make_pair(y,z));
        ans.push_back(make_pair(x,z));
    }
    swap(a[x],a[y]);
}

signed main(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),suma+=a[i],A[i]=a[i];
    for(int i=1;i<=n;i++) read(b[i]),sumb+=b[i],B[i]=b[i];
    if(suma!=sumb){
        cout<<"No\n";
        return 0;
    }
    if(n==2){
        bool state=false;
        if(a[1]==b[1]) state=true;
        if(!state){
            ans.push_back(make_pair(1,2));
            swap(a[1],a[2]);
            a[1]--;a[2]++;
            if(a[1]==b[1]) state=true;
            if(!state){
                cout<<"No\n";
                return 0;
            }
        }
    }
    else{
        sort(A+1,A+n+1);sort(B+1,B+n+1);
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                if(A[i]==a[j]){
                    if(i==j) break;
                    swap(i,j,i==1?(j==n?2:n):1);
                    break;
                }
            }
        }
        for(int l=1,r=n;l<r;){
            while(a[l]==B[l]&&l<=n) l++;
            while(a[r]==B[r]&&r>=1) r--;
            while(a[l]<B[l]||a[r]>B[r]){
                ans.push_back(make_pair(l,r));
                swap(a[l],a[r]);
                a[l]--;a[r]++;
                swap(l,r,l==1?(r==n?2:n):1);
            }
            while(a[l]==B[l]&&l<=n) l++;
            while(a[r]==B[r]&&r>=1) r--;
            while(a[l]>B[l]||a[r]<B[r]){
                swap(l,r,l==1?(r==n?2:n):1);
                ans.push_back(make_pair(l,r));
                swap(a[l],a[r]);
                a[l]--;a[r]++;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                if(b[i]==a[j]){
                    if(i==j) break;
                    swap(i,j,i==1?(j==n?2:n):1);
                    break;
                }
            }
        }
    }
    cout<<"Yes\n";
    for(int i=0;i<ans.size();i++) if(ans[i].first>ans[i].second) swap(ans[i].first,ans[i].second);
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++) cout<<ans[i].first<<" "<<ans[i].second<<endl;
    return 0;
}