欢迎访问 生活随笔!

凯发k8官方网

当前位置: 凯发k8官方网 > 编程资源 > 编程问答 >内容正文

编程问答

题目:大地的秘密 -凯发k8官方网

发布时间:2024/10/8 编程问答 0 豆豆
凯发k8官方网 收集整理的这篇文章主要介绍了 题目:大地的秘密 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题目背景
在你的帮助之下,三仙兽终于弄清楚了到北京的道路,于是他们收拾一下行装,出发了。

第一站他们要经过被成为“米不亚亚亚亚尔”的神秘森林,由于有蓬絮这位走迷宫的高手打头阵,前进的道路变平坦了很多。但当他们来到这片森林的核心地带时,还是遇到了一点点小麻烦……

题目叙述
现在他们位于神秘森林的核心部位,面前有两条主要的大道,不用说,一条通向光明,一条通向黑暗。大家当然想奔向光明,远离黑暗,可是蓬絮研究了半个时辰也研究不出个所以然。

倒是细心的花楹发现了线索,她在地上搜寻时,发现了遗落在草丛里的一张纸,纸上如是写道:

致想要寻找出口的人们:
  这里必须你们真正了解大地的运行规律,才能破解难关。
  现在,你们只需要拿这这张纸,大喊一声:“哇呱呱呱呱呱呱呱呱呱呱~”,你们前方的地面上就会出现很多的木偶士兵,他们外貌各异。你们必须把他们排布成东边一棵松树上刻纹中写出的阵列,正确的出口才会显露出来。
  正确的答案就在你们面前,只看你们能不能把握咯。

      ——米不亚亚亚亚尔之主:巴罗罗罗罗列吉

没办法,虽然这张破破烂烂发着臭气的纸看上去不像真的,死马当作活马医,三人还是照做了。没想到咒语刚说完,前方“嗡~”的一声起了巨大的烟雾。等到烟消云散,三兽定睛一看,地上果然出现了数不清的人偶。

他们开始相信这一张纸的真实性了,动作快的勇气赶忙找到附近的一棵松树。果然,上面也刻着数不请的人偶图案。

现在的任务就是如何调整木偶的顺序了。整个木偶群可以看成一列排布的,所有的 n 个木偶不尽相同,编号为 1-n。由于仙兽功力有限,每次施法只能把一个木偶移动到另两个木偶之间(可以移到队头和队尾)。

经过三个时辰的仔细研究,勇气已经把所有的木偶都正确编号完毕(勇气:累死俺也~她们两个都不干事的……)。现在他需要你告诉他,要完成调整最少需要移动多少次木偶,这样来给他个心里准备……

数据范围
对于 60% 的数据,n <= 1000
对于 100% 的数据,n <= 100000

三行,第一行一个整数 n,表示有 n 个木偶。
第二行,n 个整数(1-n),表示初始时木偶的排布。
第三行,n 个整数(1-n),表示目标木偶的排布。

一行,一个整数,表示最少移动次数。

 

 

题解:————————————————————————————————————————

赞!这道题实在是太赞了!!!

很显然,每一个人偶最多只需要移动一次便可到达正确位置。但是从样例中可以看出,有一些人偶是不需要动的,那么最终的答案便是 n 减去不需要移动的人偶数。

这道题集lis(最长不下降序列)与lcs(最长公共序列)于一身。也可以说吸收了lcs的思想,或者是lcs的变形应用。而且该题的数据范围n<=100000使得lis动态规划o(n*n)的算法超时,所以这里用需要用到lis(nlgn)的算法,这在前面我的博客上都有介绍的。

数组a[i]记录的是初始时木偶的排布,令c[a[i]]=i,所以c[]是递增的。b[i]记录的是移动后木偶的排布。求c[b[i]]数列的最长不下降序列长度。

#include
#include
using namespace std;

int a[100001],b[100001],c[100001],f[100001],n,len=1;

int find(int x,int r){
    int mid,l=1;
    while(l<=r)
    {
     mid=(l r)/2;
     if(f[mid]==x) return mid;
     if(f[mid]     if(f[mid]>x) r=mid-1;     
               }
    return l;
    }

int main()
{
    int i,j;
    scanf("%d",&n);
   
    for(i=1;i<=n;i )
    {scanf("%d",&a[i]);c[a[i]]=i;}
   
    for(i=1;i<=n;i )
    scanf("%d",&b[i]);

    memset(f,0,sizeof(f));
    f[1]=c[b[1]];
    for(i=2;i<=n;i )
    {
    j=find(c[b[i]],len);
    if(j>len) len=j;
    f[j]=c[b[i]];
    }
   
    cout<    system("pause");
    return 0;
   
    }

转载于:https://www.cnblogs.com/noip/archive/2012/01/16/2324141.html

总结

以上是凯发k8官方网为你收集整理的题目:大地的秘密的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得凯发k8官方网网站内容还不错,欢迎将凯发k8官方网推荐给好友。

网站地图