[ABC302G] Sort from 1 to 4
一道简单的性质分析题。
考虑到这个数列只有 \([1,4]\) 的数，就可以考虑有哪几种交换方案。
我们先统计出 \(t[i][j]\) 表示应该填 \(i\) 但是填了 \(j\) 的位置，注意 \(i=j\) 时 \(t[i][j]=0\)。
- 交换两个数，例如 \(t[1][2],t[2][1]\)，代价为 \(1\)，恢复两个位置。
- 交换三个数，例如 \(t[1][2],t[2][3],t[3][1]\)，代价为 \(2\)，恢复三个位置，即 \(2,3,1\) 变为 \(1,3,2\) 再变为 \(1,2,3\)。
- 交换四个数，例如 \(t[1][2],t[2][3],t[3][4],t[4][1]\)，代价为 \(3\)，恢复四个位置，交换方法如下图
由于只有 \(4\) 个不同的数，所以后面的交换方案都是浪费的。由于 \(\dfrac{2}{1}>\dfrac{3}{2}>\dfrac{4}{3}\)，所以按照 1,2,3 的操作顺序是最优的。容易发现这样一定是对的。排序可以用变量统计，操作 3 可以根据前面的操作 1,2 剩下的对数求得次数。
#include<cstdio>
#include<algorithm>
using namespace std;
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
const int N=200010;
int n,a[N],cnt[5],t[5][5],ans;
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
#endif
// Insert Code Here
scanf("%d",&n);
E(i, n)scanf("%d",a+i),++cnt[a[i]];
E(i, 4)cnt[i]+=cnt[i-1];
E(i, n)
E(j, 4)
if(i<=cnt[j]){
if(a[i]!=j)++t[a[i]][j];
break;
}
// E(i, 4){
// E(j, 4)printf("%d ",t[i][j]);
// puts("");
// }
E(i, 4)
E(j, 4){
int d=min(t[i][j],t[j][i]);
/*if(d)printf("%d %d\n",i,j),*/t[i][j]-=d,t[j][i]-=d,ans+=d;
}
// printf("%d\n",ans);
// E(i, 4){
// E(j, 4)printf("%d ",t[i][j]);
// puts("");
// }
E(i, 4)
E(j, 4)
E(k, 4){
int d=min({t[i][j],t[j][k],t[k][i]});
/*if(d)printf("d=%d\n",d),*/t[i][j]-=d,t[j][k]-=d,t[k][i]-=d,ans+=d+d;
}
int tot=0;
E(i, 4)
E(j, 4)tot+=t[i][j];
ans+=tot/4*3;
printf("%d",ans);
return 0;
}