URAL 1521 War Games 2 树状数组解决约瑟夫环，输出离队顺序

浏览数：22 / 时间：2015年06月08日

1521. War Games 2

Time limit: 1.0 second
Memory limit: 64 MB

Background

During the latest war games (this story is fully described in the problem "War games") the Minister of Defense of the Soviet Federation comrade Ivanov had a good chance to make sure personally, that an alertness of the Soviet Army under his command is just brilliant. But there was a thing, that continued to worry him. Being an outstanding commander, he realized, that only physical conditions of the soldiers were demonstrated. So the time came to organize one more war games and examine their mental capacity.

General Rascal was appointed to be responsible for the war games again. The general donated the allocated funds to the poor and went to bed free-hearted. In his dream, the tactics manual appeared to him and described a scheme, that allows to organize the war games absolutely free of charge.

Problem

In accordance with this scheme, the war games are divided into N phases; and N soldiers, successively numbered from 1 to N, are marching round a circle one after another, i.e. the first follows the second, the second follows the third, ..., the (N-1)-th follows the N-th, and the N-th follows the first. At each phase, a single soldier leaves the circle and goes to clean the WC, while the others continue to march. At some phase, the circle is left by a soldier, who is marching Kpositions before the one, who left the circle at the previous phase. A soldier, whose number is K, leaves the circle at the first phase.

Surely, Mr. Rascal cherished no hope about his soldiers‘ abilities to determine an order of leaving the circle. "These fools can not even paint the grass properly", - he sniffed scornfully and went to sergeant Filcher for an assistance.

Input

The only line contains the integer numbers N (1 ≤ N ≤ 100000) and K (1 ≤ K ≤ N).

Output

You should output the numbers of soldiers as they leave the circle. The numbers should be separated by single spaces.

Sample

input	output
5 3	3 1 5 2 4

题意：约瑟夫环问题。输入n是总人数，数到k的人离队。输出离队顺序。

做法：因为要输出在原串中的位置，所以用了树状数组加二分来找。树状数组开始每个点都初始化为1，然后离队的改为减一。对于sum（x），x是原来环的标号，sum（x）就表示当前减少了人数的环中对应的是第几个。

//树状数组  单点更新  区间查询
#include <stdio.h>
#include <string.h>
const int MAX_N=100000+5;//开到区间大小就够了
int bit[MAX_N],N;  //
 
int sum(int i)
{
	int s=0;
	while(i>0)
	{
		s+=bit[i];
		i-=i&(-i);  //感觉从底层向上加。  加减二进制末尾的1
	}
	return s;
}

void add(int i,int x)
{
	while(i<=N)
	{
		bit[i]+=x;
		i+=i&(-i);  
	}
} 
int find(int x,int n)
{
	int l=1,r=n;
	while(l<=r)
	{
		int mid=(l+r)/2;
		int tem=sum(mid);
		if(tem<x)
			l=mid+1;
		else
			r=mid-1;
	}
	printf("%d ",l);
	return l;
}
int main() 
{ 
	int n,k;
	scanf("%d%d",&n,&k);
	N=n;
	memset(bit,0,sizeof(bit));
	for(int i=1;i<=n;i++)
		add(i,1);  
	int cur = 1;
	int res = n;
	for(int i=1;i<=n;i++)
	{
		cur=(cur+k-1)%res;
		if(cur==0)
			cur=res;
		int tem=find(cur,n);
		add(tem,-1);
		res--;
	} 
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

URAL 1521 War Games 2 树状数组解决约瑟夫环，输出离队顺序