荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: selahx (MYKERNEL), 信区: ACMICPC
标 题: Re: 一道题~~~~~~
发信站: 荔园晨风BBS站 (Thu Jul 1 10:14:01 2004), 站内信件
是一道简单题来的，最主要的思想就是尽量找出和构造出多点交换一次就有两个数字
回到正确的位置的对来，这个考一点逻辑思维吧，不过其实规律也挺容易找的，我一开始
想错方向也才花了30分钟就想出来了，然后就写了一下提交，第一次就accept了，
我选c编译器的话时间是15ms，平了pku online judge这道题的时间记录了^_^
其实pku的online judge也很不错，测试返回的数据也很全面，不过他的编译器有点古怪
我提交了四次，每次都用不同的编译器，结果如下：
121864 selahx 1674 Accepted 148K 62MS C++(GCC) 1.03K 2004-07-01 05:53:18.0
121863 selahx 1674 Accepted 138K 15MS C 1.03K 2004-07-01 05:22:04.0
121862 selahx 1674 Accepted 148K 62MS C(GCC) 1.03K 2004-07-01 05:21:35.0
121861 selahx 1674 Accepted 140K 31MS C++ 1.03K 2004-07-01 05:13:37.0
我的程序如下（写得比较烦，自己写的时候都差点懵了）：
很难用描述出来具体的方法，要靠你自己去领会咯^_^～
/*
Author: Selahx.BRO
Date: 2004.7.1
Other: PKU1674
*/
#include<stdio.h>
#include<string.h>
int main()
{
int stat[10005],is[10005],stat2[10005],cases,ca,i,n,m,o,tmp;
scanf("%d",&cases);
for(ca=1;ca<=cases;ca++)
{
memset(is,0,sizeof(is));
scanf("%d",&n);
m=n;
o=0;
for(i=1;i<=n;i++)
{
scanf("%d",&stat[i]);
stat2[stat[i]]=i; //建一个反向索引表^_^
if(stat[i]==i)
{
is[i]=1;
m--;
}
}
if(m==0)
{
printf("%d\n",0);
continue;
}
for(i=1;i<=n;i++)
{
if(is[i]==1) continue;
if(stat2[i]==stat[i])
{
stat[stat2[i]]=stat2[i];
is[stat2[i]]=1;
stat[i]=i;
is[i]=1;
o+=1;
m-=2;
continue;
}
if(stat[stat[i]]==stat[stat2[i]])
{
stat[stat2[i]]=stat2[i];
is[stat2[i]]=1;
stat[stat[i]]=stat[i];
is[stat[i]]=1;
stat[i]=i;
is[i]=1;
o+=2;
m-=3;
continue;
}
tmp=stat[i];
stat[i]=i;
stat[stat2[i]]=tmp;
is[i]=1;
stat2[tmp]=stat2[i];
o++;
m--;
}
printf("%d\n",o);
}
return 0;
}
【 在 bakey (深海的鱼爱上会潜水的猫) 的大作中提到: 】
: 好象还不是很清楚`~~~可能我不大熟BFS~~~~我想的是是不是每个数字
: 如果不在正确的位置上时每次只要换一次就就可以到正确的位置上了，那么
: 每次从头开始搜索数列，看哪些数字不在它正确的位置上~~~~~~~~这样有什么问题吗？【
在 alec (AlecMonkeyKing) 的大作中提到: 】
: : understand?
--
╭―━╮
┃灵犀￤
￤一指┃
╰━―╯
※ 修改:·kaman 於 Jul 1 06:57:55 修改本文·[FROM: 210.21.224.235]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.21.224.232]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店