poj 3270 Cow Sorting 簡單的更換
如果初始狀态是
a:2 3 1 5 4 6
則目标狀态為
b:1 2 3 4 5 6且下标為初始狀态中的3 1 2 4 5 6(a[3],a[1]...)
将置換群寫成循環的形式
(2,3,1),(5,4),6就不用移動了。
移動方式2種
1:選循環内最小的數和其它len-1個數交換
2:選整個序列最小的數和循環内最小的數交換。轉到1。再換回來。
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int a[100005],b[100005];
int hash[100005];
bool vis[100005];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
for(int i=1;i<=n;i++) hash[a[i]]=i;
int ans=0;
/*
2 3 1
1 2 3----id: 3 1 2
*/
for(int i=1;i<=n;i++)
{
if(vis[i]||a[i]==b[i]) continue;
int id=i,x=a[i],len=0,mins=0x3f3f3f3f,sum=0;
while(true)
{
sum+=x;
mins=min(mins,x);
vis[id]=true;
x=b[id];
id=hash[b[id]];
len++;
if(x==a[i]) break;
}
ans+=min(sum-mins+mins*(len-1),(sum-mins+b[1]*(len-1)+2*(b[1]+mins)));
}
printf("%d\n",ans);
}
return 0;
}
i位置相應a[i]位置。求相應K次之後的字元串是什麼,(k非常大)
相同和上題一樣暴力尋找置換循環。比如
4 5 3 7 2 8 1 6 10 9 可分成(4,7,1),(5,2),(3),(8,6),(10,9),找到了每塊循環的長度len之後
對每塊循環模拟求k%len次即可了。
代碼有點不同,但思想就是這樣。
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int a[205];
int sum[205];
char str[205];
char tmp[205];
int v[205][205];
int main()
{
int cas,n,k;
while(scanf("%d",&n)!=EOF&&n)
{
for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=0;
for(int i=1;i<=n;i++)
{
int j=a[i];
if(i==j) {v[i][sum[i]++]=i;continue;}
v[i][sum[i]++]=i;
while(i!=j)
{
v[i][sum[i]++]=j;
j=a[j];
}
}
while(~scanf("%d",&k)&&k)
{
getchar();
gets(str+1);
for(int i=strlen(str+1)+1;i<=n;i++) str[i]=' ';
for(int i=1;i<=n;i++) tmp[ v[i][k%sum[i]] ]=str[i];
tmp[n+1]='\0';
puts(tmp+1);
}
puts("");
}
return 0;
}