poj 2886 Who Gets the Most Candies? 線段樹動態求第k大的數

poj 2886 Who Gets the Most Candies? 線段樹動態求第k大的數

題意：

n個小孩站一圈，每個小孩拿一個數字，從第k個孩子開始出局，然後下一個出局的孩子是剛剛出局的孩子之前或之後第v個（剛剛出局的孩子的數字是+v則之後v個，-v則之前v個），這樣所有孩子終將出局，第p個出局的孩子得f(p)分，f(p)定義為p的因子個數。求分數最高的孩子。

分析：

設順時針為正方向，關鍵是模擬出每次出局的孩子是剩下的孩子中的正方向的第幾個，設當前要出局的是第k個，然後要求出第k個小孩的下標（pos）以便下一次計算下一個出局的孩子是第幾個,這些步驟可用線段樹維護。

代碼：

//poj 2886
//sep9
#include 
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);
	else
		return 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;
			else
				k=((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]);
	}	
}