[Codeforces1148C]Crazy Diamond——构造

红太狼 2022-01-05 15:17 217阅读 0赞

# 题目链接： #

[\[Codeforces1148C\]Crazy Diamond][Codeforces1148C_Crazy Diamond]

# 题目大意： #

给出一个$1\\sim n$的排列要求将其排序，每次能交换两个位置的数当且仅当这两个位置下标差的绝对值大于等于$\\frac\{n\}\{2\}$。要求输出一组操作数不大于$5n$的方案并保证一定有解。

先不考虑操作需要的限制条件，那么要将排列排好序只需要第$i$次将$i$与下标为$i$的那个数调换一下即可。

现在有了限制条件显然不能直接调换，我们考虑借助别的数来完成这两个数的交换。

假设需要交换的两个位置的下标分别为$x$和$y$且$y>x$。

当$\\frac\{n\}\{2\}\\le y-x$时，直接交换即可。

当$x>\\frac\{n\}\{2\}$时，显然$x,y$都能和$1$位置交换：

$1,x,y$

$x,1,y$

$y,1,x$

$1,y,x$

当$y\\le \\frac\{n\}\{2\}$时，$x,y$都能和$n$位置交换，方法同上。

当$x\\le \\frac\{n\}\{2\},y>\\frac\{n\}\{2\}且y-x<\\frac\{n\}\{2\}$时，显然只依靠$1$或$n$无法完成，但$1$和$y$能交换，$x$和$n$也能交换：

$1,x,y,n$

$y,x,1,n$

$y,n,1,x$

$x,n,1,y$

$1,n,x,y$

$1,y,x,n$

可以发现这样操作对于每个点最多需要$5$次操作就能使它归位，所以$5n$次操作内一定能完成。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<vector>
    #include<cstdio>
    #include<bitset>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    int n,m;
    int a[300010];
    int b[300010];
    int ans[1500010][2];
    int cnt;
    void get(int x,int y)
    {
    	ans[++cnt][0]=x,ans[cnt][1]=y;
    	b[a[x]]=y;
    	b[a[y]]=x;
    	swap(a[x],a[y]);
    }
    void solve(int x,int y)
    {
    	if(x==y)return ;
    	if(x>y)swap(x,y);
    	if(y-x>=m)get(x,y);
    	else if(x>m)
    	{
    		get(1,x);
    		get(1,y);
    		get(1,x);
    	}
    	else if(y<=m)
    	{
    		get(y,n);
    		get(x,n);
    		get(y,n);
    	}
    	else
    	{
    		get(1,y);
    		get(x,n);
    		get(1,n);
    		get(1,y);
    		get(x,n);
    	}
    }
    int main()
    {
    	scanf("%d",&n);m=n/2;
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&a[i]);
    		b[a[i]]=i;
    	}
    	for(int i=1;i<=n;i++)
    	{
    		solve(i,b[i]);
    	}
    	printf("%d\n",cnt);
    	for(int i=1;i<=cnt;i++)
    	{
    		printf("%d %d\n",ans[i][0],ans[i][1]);
    	}
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10962181.html

[Codeforces1148C_Crazy Diamond]: https://codeforces.com/problemset/problem/1148/C