本文从WordPress迁移而来, 查看全部WordPress迁移文章
二分
题意:有n个人排成一列,给出前k个人的数字,从第k+1个人开始,给他们分配数字,分配的方法是取当前没有出现过的最小正整数,例如8人,前3人的数字为3 5 8,第4到第8个人的数字分别为1 2 4 6 7,整个序列为3 5 8 1 2 4 6 7
数据很大,不可能模拟
- 留意到一点,因为是取最小的没用过的正整数,所以我们可以先把所有可能用的正整数保存下来,按区间保存
- 例如已经用了3 5 8,没用的就是
1 | [1,2] 2个 |
现在
要为第k+1个人分配数字,那么可以立刻知道是分配1,因为1是第1个没有用过的
要为第k+5个人分配数字,可以立刻知道是7,因为7是第5个没有用过的数字
所以要为第m个数字分配数字,在上面没有用过的数字表里面找,先找到它在哪一块,再找到是哪一块的第几个,其中找在哪一块,用二分即可
1 |
|