月份：2018年11月

//TODO:咕*3定律 在todolist里待了3周以上的任务就不可能再被完成了

题源:2017蓝桥杯国赛

基本问题描述：
已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。而问题一般是判断第k个出列或最后出列的人的编号.

有些人在解决这类问题时会把编号视为0~n-1,最后将结果+1而得原问题的解,但在此我就不这样做了.

解题思路:

此题最简单的做法可以使用模拟法完成,但不论是用数组模拟还是链表模拟,复杂度都比较高(链表模拟法每次删人需要迭代n次,总复杂度为O(mn),而数组模拟法复杂度甚至更高).

该题问题的关键在于当有人被T出后队列中剩余的编号列表就不再连续了,此时再想使用数值计算的方法难以得到下一个位置,不得已才需要使用模拟的办法得到位置.

另一种办法是每次去除人后将新环的编号重排,这样编号顺序就再次连续了,而我们所要做的就是得到新编号与旧编号之间的对应关系计算方法(以便最后能够回推得到最终的答案).这样的话寻找第k次删除人的编号问题就变成了从其第k-1次重排的编号中回推得到它在原始队列中的…编号,复杂度只有O(k)/O(n)(但是这有一个问题,如果要按顺序得出每个出列的人的编号,这样做的复杂度就没有什么优势了).

举例来说:

起始n=10,m=6

初始情况为:

1   2   3   4   5   6   7   8   9   10

删除一人后:

1 2 3 4 5 ① 7 8 9 10

队列重排:

5 6 7 8 9 ① 1 2 3 4

再删一人:

5 ② 7 8 9 ① 1 2 3 4

我们现在要找到②处在原始序列中对应的编号,首先发现它在新队列中编号为6,而计算首次删除的①在队列中编号也为6,即新队列的编号是在前队列的基础上+6,那么将其相加后再对前队列的总人数求余即可得到他在前队列中的编号了((6+6)%10).

以此类推我们也可以从第k次删除后的情况反推出其在初始时的位置.

递归版代码:

(写个屁,自己根本就不懂

• 如下，在多线程环境下，synchronized块中的方法获取了lock实例的monitor，如果实例相同，那么只有一个线程能执行该块内容
  public class Thread1 implements Runnable { Object lock; public void run() { synchronized(lock){ ..do something } } }

  1 2 3 4 5 6 7 8

  public class Thread1 implements Runnable {    Object lock;    public void run() {          synchronized(lock){          ..do something        }    } }

• 直接用于方法： 相当于上面代码中用lock来锁定的效果，实际获取的是Thread1类的monitor(equal to synchronized(this)?)(具体来说是为了防止多个thread同时调用一个同一对象的该方法)。更进一步，如果修饰的是static方法，则锁定该类所有实例。
  public class Thread1 implements Runnable { public synchronized void run() { ..do something } }

  1 2 3 4 5

  public class Thread1 implements Runnable {    public synchronized void run() {           ..do something    } }