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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ2182Lost Cows题解  

2014-03-25 21:19:26|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

丢失的牛

BY   LGS

题目大意:N头牛排在一列.告诉你这一列的第i头牛前面有多少头编号比自己小的牛.(2<=i<=N)明显第一头牛前面为0;求这一列牛的编号.

题解:我看了网上的题解才会做.先倒推一下,最后一头牛的编号一定是A[N]+1,倒数第二头牛的编号一定是前N-1个里牛的A[N-1]+1大的数字.so on;这题貌似暴力可以过N^2,但是如果N比较大,这时需要用到线段树.记录某个区间左儿子的个数和右儿子的个数.每次查询就一定是LOG(N),效率为N*log(N);

 

总结:线段树+倒推

 

代码:

  • Source Code
  • #include<cstdio>
    #define maxn 40000
    using namespace std;
    int i,j,n,m,ans[maxn],a[maxn];
    bool f[maxn];
    struct node{int l,r,ls,rs;}tree[maxn];
    void build(int a,int b,int tot)
     {
     tree[tot].l=a;tree[tot].r=b;
     if (a==b) {tree[tot].ls=1;return;}
     int mid=(a+b)/2;
     build(a,mid,tot*2);build(mid+1,b,tot*2+1);
     tree[tot].ls=tree[tot*2].ls+tree[tot*2].rs;
     tree[tot].rs=tree[tot*2+1].ls+tree[tot*2+1].rs;
     }
    void search(int k,int w)
     {
     if (tree[w].l==tree[w].r) {ans[i]=tree[w].l;tree[w].ls=0;return;} 
     if (k<=tree[w].ls) search(k,w*2);
         else search(k-tree[w].ls,w*2+1);
     tree[w].ls=tree[w*2].ls+tree[w*2].rs;
     tree[w].rs=tree[w*2+1].ls+tree[w*2+1].rs;
     }
    int main()
    {
     scanf("%d",&n);
     for (i=2;i<=n;i++) {scanf("%d",&a[i]);a[i]++;}
    build(1,n,1);
    a[1]=1;
    for (i=n;i>=1;i--) search(a[i],1);
    
    for (i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
    }
  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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