注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

奶牛排队(reorder)解题报告  

2015-07-28 09:35:17|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        【题目大意】

农夫fj有N (1 <= N <= 100)条编号为1..N的奶牛按照数组A(i)站成一排,但是为了拍照需要要把这些奶牛按照所谓的循环圆进行调整为数组B(i)排队。

例如,奶牛们初始是按照A = 5 1 4 2 3排队,为了拍照最后要调整为B = 2 5 3 1 4,调整的方法是,具体循环圆如下:在初始A数组奶牛5是排在第一位的,在B数组是排在第2,那么奶牛5就调到A数组的第2个位置取代奶牛1,奶牛1在B数组时排在第4个位置,那么奶牛1就调到A数组第4个位置取代奶牛2,奶牛2在B数组排在第1个位置,那么奶牛2就调到A数组第1个位置,因为第1个位置是奶牛5的起始位置,那么这个循环圆调整结束,这个循环圆由5、1、2组成而且他们都最终到达了最终位置。剩下由奶牛4开始,因为奶牛4在B数组排在第5个位置,那么奶牛4在A数组调到第5个取代奶牛3,奶牛3在B数组排在第3个位置,那么奶牛3在A数组调到第3个位置,这个位置刚好是奶牛4的起始位置,这样奶牛4、3也是一个循环圆。通过这两个循环圆,奶牛从初始的A数组调整到最终的B数组位置。

题目有点长奶牛排队(reorder)解题报告 - 杨鸿飞 - 一个叫杨鸿飞的人的博客

【解题思路】

以题目样例为例,模拟一下查找一个循环圆1,2,5的过程:

奶牛排队(reorder)解题报告 - 杨鸿飞 - 一个叫杨鸿飞的人的博客
        5先把2的位置占了,2把1的位置占了,1把5的位置占了,1又找到了5,所以1,2,5是一个循环圆。所以,我们应该在开一个C数组:表示一个数在A数组的位置,通过这个位置就知道谁把谁占了,所以C数组是这样的:
        下标:1        2        3        4        5
                   在       在      在      在      在 
                   第       第      第      第      第           
        内容:2        4        5        3        1
                   位      位       位      位       位     
在处理一下关系,就行了。 
下为程序:
#include<iostream>
#include<fstream>
using namespace std;
int a[110],b[110],c[110],f[110];
int main()
{
 freopen("reorder.in","r",stdin);
    freopen("reorder.out","w",stdout);
 int i,n,ans=0,p,s,sum,max=0;
 cin>>n;
 for (i=1; i<=n; i++) cin>>a[i];
 for (i=1; i<=n; i++) cin>>b[i];
 for (i=1; i<=n; i++)
  for (int j=1; j<=n; j++)
   if (b[i]==a[j]) c[i]=j;      //C数组
 for (i=1; i<=n; i++)
  if (f[b[i]]==0)   //有没有用过
  {
   f[b[i]]=1; sum=1; s=c[i]; p=b[s];
   while (p!=b[i])
   {
    f[p]=1;
    s=c[s];       //s代表位置
    p=b[s];      //p代表是谁占了位置
    sum++;     //长度
   }
   if (sum>max) max=sum;
   ans++;
  }
 cout<<ans<<" "<<max;
 return 0;
}

 

  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018