当前位置: 代码迷 >> 综合 >> poj 2886 Who Gets the Most Candies? 线段树动态求第k大的数
  详细解决方案

poj 2886 Who Gets the Most Candies? 线段树动态求第k大的数

热度:79   发布时间:2024-01-19 05:45:37.0

题意:

n个小孩站一圈,每个小孩拿一个数字,从第k个孩子开始出局,然后下一个出局的孩子是刚刚出局的孩子之前或之后第v个(刚刚出局的孩子的数字是+v则之后v个,-v则之前v个),这样所有孩子终将出局,第p个出局的孩子得f(p)分,f(p)定义为p的因子个数。求分数最高的孩子。

分析:

设顺时针为正方向,关键是模拟出每次出局的孩子是剩下的孩子中的正方向的第几个,设当前要出局的是第k个,然后要求出第k个小孩的下标(pos)以便下一次计算下一个出局的孩子是第几个,这些步骤可用线段树维护。

代码:

//poj 2886
//sep9
#include <iostream>
using namespace std;
const int maxN=500010;
int n,ids;
int ans[maxN];
struct Node
{int v;char name[16];
}child[maxN];struct seg_tree
{int l,r,sum;	
}T[maxN*4];void build(int l,int r,int k)
{T[k].l=l;T[k].r=r;T[k].sum=r-l+1;if(l==r)return ;int mid=(l+r)>>1;build(l,mid,2*k);build(mid+1,r,2*k+1);
}void ini()
{memset(ans,0,sizeof(ans));for(int i=1;i<=n;++i){++ans[i];for(int j=2*i;j<=n;j+=i)++ans[j];}	ids=1;for(int i=2;i<=n;++i)if(ans[i]>ans[ids])ids=i; 
}int update(int k,int x)
{--T[x].sum;if(T[x].l==T[x].r)return T[x].l;if(T[2*x].sum>=k)return update(k,2*x);elsereturn update(k-T[2*x].sum,2*x+1);					
}int main()
{int i,k,mod;while(scanf("%d%d",&n,&k)==2){ini();		for(int i=1;i<=n;++i)scanf("%s%d",child[i].name,&child[i].v);build(1,n,1);	mod=T[1].sum;int pos=0;child[0].v=0;n=ids;while(n--){if(child[pos].v>0)k=((k+child[pos].v-2)%mod+mod)%mod+1;elsek=((k+child[pos].v-1)%mod+mod)%mod+1;		pos=update(k,1);mod=T[1].sum;}printf("%s %d\n",child[pos].name,ans[ids]);}	
}