首页 > 代码库 > POJ 2886 Who Gets the Most Candies? （线段树）
POJ 2886 Who Gets the Most Candies? （线段树）
【题目链接】 http://poj.org/problem?id=2886
【题目大意】
一些人站成一个圈，每个人手上都有一个数字，
指定从一个人开始淘汰，每次一个人淘汰时，将手心里写着的数字x展示
如果x是正数，则淘汰右手边第x个人，否则淘汰左手边地-x个人。
每个人淘汰的时候将获得积分，积分的多少取决于他是第几个淘汰的，
积分为淘汰的顺序数拥有的因子数量
输出积分最高的人和其积分
【题解】
首先，我们计算出第几个淘汰的人分数最高，那么我们只要模拟到这个人淘汰即可
在处理中，寻找下一个人时我们可以用线段树求kth的方法求出这个人的位置，顺序处理即可。
【代码】
#include <cstdio>#include <cstring> using namespace std;const int N=500010;int n,k,T[N*4],m,id,ans[N];struct data{int val;char name[20];}p[N];void build(int x,int l,int r){ T[x]=r-l+1; if(l==r)return; int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r);}int update(int key,int x,int l,int r){ T[x]--; if(l==r)return l; int mid=(l+r)>>1; if(T[x<<1]>=key)return update(key,x<<1,l,mid); return update(key-T[x<<1],x<<1|1,mid+1,r);}void GetID(){ memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j+=i)ans[j]++; }int mx=ans[id=1]; for(int i=2;i<=n;i++)if(ans[i]>mx){mx=ans[i];id=i;}}int main(){ while(~scanf("%d%d",&n,&k)){ build(1,1,n); GetID(); for(int i=1;i<=n;i++)scanf("%s%d",p[i].name,&p[i].val); int mod=T[1],pos=0; p[0].val=0; m=id; while(m--){ if(p[pos].val>0)k=((k-1+p[pos].val-1)%mod+mod)%mod+1; else k=((k-1+p[pos].val)%mod+mod)%mod+1; pos=update(k,1,1,n); mod=T[1]; }printf("%s %d\n",p[pos].name,ans[id]); }}POJ 2886 Who Gets the Most Candies? （线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。