顾客是上帝（Keep the Customer Satisfied, ACM/ICPC SWERC 2005, UVa1153）
题目描述：求最少的交换次数，使给定的数字序列能成为环。
解题思路：最少交换次数的环一定是某一个数为起点的环。那便枚举1~n使之作为起点。注意环可以使顺时针增加也可以减少，所以需要再反序枚举，求出最小的交换次数。求最小的交换次数的方法是,让alien[i]=i，否则交换，此时cnt++。至于为什么这就是最小的交换次数，我现在还不能确定我的证明是正确的，现在想到的证明是 ：若把一个序列通过交换变为升序列，每次把i交换到位置i上，则一次交换至少可以保证一个位置上数字在该在的位置上，最多是使得两个数字在在该在的位置（如数字1在位置2，数字2在位置1，交换后，一次交换可以使两个数字在该在的位置）。如果不这样做，可以明确知道的是，对于任何交换，一次交换最多会完成两个位置，假设不是直接将数字i放到位置i上，而是经过了1次中间步骤，如果 下一步骤正好可以一次交换完成两个位置，那么对于这两个数字相当于两次操作完成两个位置，而上面的交换是一次交换可以完成>=1的位置，所以还是上面的交换是最优的，
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=500+10;
int pos[maxn],alien[maxn],n,cpy_pos[maxn],cpy_alien[maxn];
int solve(int q,int d)
{
int cnt=0,p;
if(d==1) p=0;
else p=n;
for(int i=1; i<=n; i++)
{
int x=(p+q-1)%n+1;
if(cpy_alien[i]!=x)
{
cnt++;
cpy_alien[cpy_pos[x]]=cpy_alien[i];
cpy_pos[cpy_alien[i]]=cpy_pos[x];
cpy_alien[i]=x;
cpy_pos[x]=i;
// swap(cpy_pos[cpy_alien[i]],cpy_pos[x]);
// swap(cpy_alien[i],cpy_alien[cpy_pos[x]]);
//此处不能简单的用swap交换，因为其值和下标是有联系的。
}
q+=d;
}
return cnt;
}
int main()
{
while(cin >> n&&n)
{
for(int i=1; i<=n; i++)
{
scanf("%d",&alien[i]);
pos[alien[i]]=i;
}
int ans=INF;
for(int i=1; i<=n; i++)
{
memcpy(cpy_alien,alien,sizeof(alien));
memcpy(cpy_pos,pos,sizeof(pos));
ans=min(ans,solve(i,1));
}
for(int i=1; i<=n; i++)
{
memcpy(cpy_alien,alien,sizeof(alien));
memcpy(cpy_pos,pos,sizeof(pos));
ans=min(ans,solve(i,-1));
}
cout << ans << endl;
}
return 0;
}
注意上面的交换过程，顺序非常重要，上面的赋值不能影响下面的赋值。而且这种方法经常用到。
投递安利等公司10个岗位 >
