约瑟夫问题(SJTU OJ 1038)

Description

话说二哥当年学习数据结构的时候遇到了那道猴子报数的题目,其实这就是经典的约瑟夫问题。

可是当年的二哥还是个毛头小子,只会用模拟的方法,而其他同学却使用了一些令二哥完全摸不到头脑的方法。

……二哥一怒之下改了题目……

话说当年花果山的猴子要选大王,选举办法如下:

所有猴子按1-M编号围坐一圈,二哥站在圈中心,由二哥指定一个整数Kn,

之后猴子们从1号开始按顺序报数,报到Kn的猴子退出到圈外,二哥再报出一个整数Kn+1,

然后由刚刚退出的猴子的下一只猴子再开始报数,如此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王。

由于二哥希望通过此种方法控制花果山,所以现在二哥把他制定的整数序列告诉你,希望你帮他预先算出那只猴子会成为大王。

Input Format

第一行 一个整数M,表示一共有M只猴子

第二行到第M行,每行一个整数 表示二哥即将指定的M-1个整数。这些数都大于0。

Output Format

一个整数,表示最后剩下那只猴子的编号。

Hint

对于40%的数据,M<=1000, K<=1000

对于70%的数据,M<=10000, K<=10000

对于100%的数据,M<=10000, K<=100000000

Sample Input

5
1
2
3
4

Sample Output

4

Solution

用链表解决这个问题。需要注意以下两点:

  1. 单向循环链表可以相对节省空间。
  2. 单向链表在请求删除第一个数据时,由于不知道前一个结构体,所以我采用绕一圈的方式,其实也可以使用双向循环链表,各有利弊。
  3. 减少时间复杂度,在每次都记录一下剩余的链表结构体的数量,用余数来确定指定的位置,由此保证每一次操作,都控制在一次完整的循环链表遍历之内。
//
// main.c
// 1038
//
// Created by Oscar on 21/09/2017.
// Copyright © 2017 刘丰瑞. All rights reserved.
//



#include <stdio.h>
#include <stdlib.h>


typedef struct Lnode{
int num;

struct Lnode *next;
}LinkList;

void createList (LinkList *L, int n) {
LinkList *s,*r,*p;
int i;
L->num = 1;
r = L;
for (i = 2 ; i<=n; i++) {
s = (LinkList*)malloc(sizeof(LinkList));
s->num = i;
r->next = s;
r = s;
}
r->next = L;

}


void findList (LinkList *L, long long int n, long long int *remain){
int a;
LinkList *f;
if (n == 1) {
for (a=1; a<*remain; a++) {
L=L->next;
}
}else {
for (a=0; a<n-1; a++) {
L=L->next;
}
}
f = L->next;
L->next = L->next->next;
L = L->next;
*remain -= 1;
free(f);
}

int main(int argc, const char * argv[]) {
int n,m,i,p=0,q=0,a,sum;
int k;
LinkList *monkey;
LinkList *f;
scanf("%d",&sum);
monkey = (LinkList *)malloc(sizeof(LinkList));

createList(monkey, sum);
k=sum;
for (m = 1; m<sum; m++) {
if (m==sum-1) {
scanf("%d",&i);
}else{
scanf("%d\n",&i);
}

i = i%k;
if (i == 0) {
i = k;
}

if (i == 1) {
for (a=1; a<k; a++) {
monkey=monkey->next;
}
}else {
for (a=0; a<i-2; a++) {
monkey=monkey->next;
}
}
f = monkey->next;
monkey->next = monkey->next->next;
monkey = monkey->next;
k -= 1;
free(f);
}

printf("%d ", monkey->num);
return 0;
}