贺大和他的朋友们

贺大和他的朋友们

时间： 1ms        内存：64M

描述：

贺大和他的朋友们参加一个户外训练营。训练营的项目包括爬雪山、冬泳、孤岛生存、蹦极、跳伞等极限活动。训练营规定每天淘汰表现最差的一个人。最差人选由参加活动的营员们投票决定。最后剩下的一个人将获得训练营提供的500万大奖。

贺大和他的朋友们不想因为投票伤害彼此的友谊，于是他们决定通过做游戏来决定每天出局的人选。游戏规则是这样的：将贺大和他的朋友们 n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人出局，不再参加接下来的活动。剩下的人继续参加活动，最后出局的一个人是大奖获得者。 请输出最后一个人的编号。

输入：

输入数据有多组，每组占一行，包含正整数n和m（1<=n,m<=10000）。

输出：

对于每组输入数据，输出大奖获得者的编号，每个测试实例占一行。

示例输入：

5 3
100 3

示例输出：

4
91

提示：

参考答案（内存最优[748]）：

#include<stdio.h>
int main()
{
    int n,m,i,s;
	while(scanf("%d %d",&n,&m)==2)
	{
		s=0;
		for(i=2;i<=n;i++)
			s=(s+m)%i;
		printf("%d\n",s+1);
	}
	return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
using namespace std;
struct monkey
{
	int num;
	monkey *next;
};
monkey *head,*last;
void create(int n)
{
	int i;
	monkey *p,*q;
	p=new monkey;
	p->num=1;
	p->next=NULL;
	head=p;
	q=p;
	for(i=2;i<=n;i+=1)
	{
		p=new monkey;
		p->num=i;
		q->next=p;
		q=p;
		p->next=NULL;
	}
	last=q;
	last->next=head;
}

void select(int m)
{
	int x=0;
	monkey *p,*q;
	q=last;
	do	
	{    
		p=q->next;	
		x=x+1;			
		if(x % m==0)	                 
		{			                     
			q->next=p->next;       
			delete p;	             
			p=NULL;  
		}	             
		else q=p;		
	} while(q!=q->next);
	head = q;		
}				



int main()
{
	int n,m;			
	head=NULL;			
	while(cin>>n>>m)		
    {
		create(n);			
		select(m);
		cout<<head->num<<endl;
	}
	
	return 0;
}				

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。