程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 2886 Who Gets the Most Candies? 線段樹動態求第k大的數

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

編輯:關於C++

題意:

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]);
	}	
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved