荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: alec (AlecMonkeyKing), 信区: ACMICPC
标 题: Re: 一道题~~~~~~
发信站: 荔园晨风BBS站 (Thu Jul 1 13:12:50 2004), 站内信件
1) every number can be changed at most once
2) there only one local for the number you want to change
(if you want to save time)
e.g
2 3 5 4 1
~->when you want to change this number, it must change to
3 2 5 4 1
3) the only way that we can save the times of change, that is
change something like this 1 5 3 4 2 ->1 2 3 4 5, both
2 and 5 in the right place after change
4) we need more numbers like what i said in the (3)
if there some numbers like that in the list already, what we should
do is change them first, after this, we just follow the numbers
to change it to, we check if there is any numbers like (3) after
change
5) there only one local for the number to change, hence we need not
thought about something like this: 1 3 5 4 2, change the 5<->2 fist
1 3 2 4 5, then 3<->2, a link.
code:
#include <iostream>
using namespace std;
const int maxn=10005;
int save[maxn];
int n,ans;
int main(){
int tt,i,ii,t,l;
cin>>tt;
for (ii=0;ii<tt;ii++){
cin>>n;
ans=0;
for (i=1;i<=n;i++){
cin>>save[i];
if (save[i]==i) save[i]=0;
}
l=n;
for (i=1;i<=n;i++){
if (!l) break;
if (save[i]){
if (save[save[i]]==i){
ans++;
save[save[i]]=0;
save[i]=0;
l-=2;
continue;
}
t=save[save[i]];
save[save[i]]=0;
save[i]=t;
ans++;
l--;
i--;
}
}
cout<<ans<<endl;
}
return 0;
}
【 在 alec (AlecMonkeyKing) 的大作中提到: 】
: ok your solution is ok
: but...... need not that trouble
: i will show you the proof
: wait
: 【 在 selahx (MYKERNEL) 的大作中提到: 】
: : 不会有0，把数据全加1
: : 8 9 4 5 3 7 1 10 2 6
: : 我的结果是7
--
Computer Science is no more about computers
than Astronomy is about telescopes.
-- E. W. Dijkstra
Alec
※ 修改:·alec 於 Jul 1 14:01:17 修改本文·[FROM: 192.168.58.237]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.58.237]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店