The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 2886 Who Gets the Most Candies? 线段树,在环中求第k个空闲的位置

很高兴在完全没有参考任何代码的前提下通过此题,呵呵,就是代码比较猥琐,跑得也比较慢,2700MS,超过时限的一半了。
此题应该还有继续提升的空间,我想了想,insert函数和query其实是可以放在一起的。另外网上的方法用了反素数 这样可以减少插入的次数,应该也能剪去一下时间。下次试试。^_^
顺便用此题做为POJ 500题纪念

#include<iostream>
using namespace std;

int n,k;
struct person
{
    
char s[10];
    
int p;
}
a[500010];
int dp[500010];

void init()
{

    
int i,j;
    
for(i=1;i<=500000;i++)
        
for(j=1;i*j<=500000;j++)
            dp[i
*j]++;
}


const int maxn=500010;
struct node
{
    
int l,r;
    
int cnt;
}
tree[maxn*3];

void build(int k,int l,int r)
{

    tree[k].l
=l;tree[k].r=r;
    tree[k].cnt
=0;
    
if(l==r) return;
    
int mid=(l+r)>>1;
    build(k
*2,l,mid);
    build(k
*2+1,mid+1,r);
}


void insert(int i,int k)
{
    tree[i].cnt
++;
    
if(tree[i].l==tree[i].r) return;
    
else 
    
{
        
int mid=(tree[i].l+tree[i].r)>>1;
        
if(k<=mid)
            insert(i
*2,k);
        
else 
            insert(i
*2+1,k);
    }

}


int query(int i,int k)
{
    
if(tree[i].cnt==0&&tree[i].r-tree[i].l+1==k)
        
return tree[i].r;
    
int l=tree[i*2].r-tree[i*2].l+1-tree[i*2].cnt;
    
int r=tree[i*2+1].r-tree[i*2+1].l+1-tree[i*2+1].cnt;
    
if(k<=l)
        
return query(i*2,k);
    
else
        
return query(i*2+1,k-l);
}


int query2(int i,int l,int r)
{

    
if(tree[i].l==l&&tree[i].r==r)
        
return tree[i].r-tree[i].l+1-tree[i].cnt;
    
int mid=(tree[i].l+tree[i].r)>>1;
    
int res=0;
    
if(r<=mid)
        res
+=query2(i*2,l,r);
    
else if(l>mid)
        res
+=query2(i*2+1,l,r);
    
else 
    
{
        res
+=query2(i*2,l,mid);
        res
+=query2(i*2+1,mid+1,r);
    }

    
return res;
}



int main()
{
    
int i,j;
    init();
    
int res=dp[1];
    
int mark=k;
    
while(scanf("%d%d",&n,&k)!=EOF)
    
{
        
int pos;
        
int res=dp[1];
        
int mark=k;
        build(
1,1,n);
        
for(i=1;i<=n;i++)
            scanf(
"%s%d",a[i].s,&a[i].p);
        
int l,r;
        
int t=k;
        pos
=k;
        insert(
1,k);
        
for(i=2;i<=n;i++)
        
{
            t
=pos;
            
if(t>1)l=query2(1,1,t-1);
            
else l=0;
            
if(t<n)    r=query2(1,t+1,n);
            
else r=0;

            
if(a[t].p%(l+r)!=0)
                a[t].p
%=(l+r);

            
else if(a[t].p>0)
                a[t].p
=l+r;
            
else 
                a[t].p
=-(l+r);
            
if(a[t].p>0&&a[t].p<=r)
                pos
=query(1,l+a[t].p);
            
else if(a[t].p<0&&l+a[t].p>=0)
                pos
=query(1,l+a[t].p+1);
            
else if(a[t].p>0&&a[t].p>r)
                pos
=query(1,a[t].p-r);
            
else 
                pos
=query(1,l+r-abs(l+a[t].p)+1);
            
if(res<dp[i])
            
{
                mark
=pos;
                res
=dp[i];
            }

            insert(
1,pos);
        }

        printf(
"%s %d\n",a[mark].s,res);
    }

    
return 0;
}

posted on 2010-04-14 00:41 abilitytao 阅读(1373) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理