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

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【trick】【cf】 contest/189/problem/C  

2012-05-11 02:32:31|  分类: ACM_其他 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
链接:http://www.codeforces.com/contest/189/problem/C

题目大意:
给出n (1?≤?n?≤?2·105)  个数的序列a,含1-n, 然后给出另外一个n个数的序列b,含1-n,
按照给定的移动规则:
1.每次只能移动最后一个数字
2.最后一个数字可以insert到前面的数字之间,或者直接移动到最前面

求,从序列a按照这个规则变为序列b的最少次数


分析:
向来都不太擅长这种题目,==!
因为每次都是从最后一个开始移动,所以,最少的情况下,是每个数字最多移动了1次就可以了,从前向后扫描,不同的数字表示需要移动1次。

方法1:
ans = 0;
for( i = 1;i <= n;i ++)
     if (a[i] != b[i])
        ans++


方法2:

int a[200010], b[200010], n, x;
int main()
{
scanf
("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
{
scanf
("%d", &x);
b
[x] = i;
}
for (int i = 1; i <= n; ++i) a[i] = b[a[i]];
int res = 0;
for (int i = 1; i < n; ++i)
if (a[i] > a[i + 1])
{
res
= n - i;
break;
}
printf
("%d\n", res);

return 0;
}


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

历史上的今天

评论

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

页脚

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