题目描述

难度分:$1500$

输入$n(1 \leq n \leq 10^{18})$，表示有$n$颗石子。

$A$和$B$取石子，每次$A$先取走$k$颗石子（石子剩余个数不足$k$则全取），然后$B$取走$\lfloor \frac{rest}{10} \rfloor$颗石子（其中$rest$表示剩余石子数，$\lfloor . \rfloor$表示对$.$向下取整）。如此交替取石子，直到石子全部取完为止。

输出最小的$k$，使得$A$总共可以取走至少一半的石子，即$\lceil \frac{n}{2} \rceil$颗石子，其中$\lceil . \rceil$表示对$.$向上取整。

输入样例

68

输出样例

3

算法

二分答案

可以比较容易发现单调性，$k$越大$A$是越有可能获得超过一半的石子的。

分析一下这个游戏过程，$A$每次都取$k$，规律很明显。而$B$第一次取$\lfloor \frac{n-k}{10} \rfloor$，第二次取$\lfloor \frac{n - k - \lfloor \frac{n-k}{10} \rfloor}{10} \rfloor$，很容易就发现$B$的收益成指数级别下降。模拟这个游戏过程只需要$log_{10}n$不到的轮次就能因为$B$的收益为$0$而停止，把剩下石子直接加到$A$的所得上即可，这样一来$check$函数就可以在$O(log_{10}n)$的时间复杂度下完成任务。

外面就在$[1,n]$的范围内进行二分答案，时间复杂度是$O(log_2n)$。对于给定的$k$，能够使得$A$的所得不少于总数的一半就记录答案往左搜索看有没有更小的$k$，否则就往右搜索。

复杂度分析

时间复杂度

根据算法的游戏过程分析，二分的时间复杂度为$O(log_2n)$，$check$的时间复杂度为$O(log_{10}n)$。算法整体的时间复杂度为$O(log_2nlog_{10}n)$，大概就是$O((logn)^2)$级别。

空间复杂度

仅使用了有限几个变量，因此算法的额外空间复杂度为$O(1)$。

$python$代码

n = int(input())

def check(k: int) -> bool:
    a, b, rest = 0, 0, n
    while rest >= k:
        a += k
        rest -= k
        gain = rest // 10
        b += gain
        rest -= gain
        if gain == 0:
            break
    a += rest
    return a*2 >= n

l, r = 1, n
while l < r:
    mid = l + r >> 1
    if check(mid):
        r = mid
    else:
        l = mid + 1
print(r)