丢棋子问题

二分法，奇数-1对半，偶数对半-1。多于1个棋子最后要-1。
这个算法好像有点问题，但是总能通过一部分样例。
所以暴力硬编码了……
用例通过率: 100.00% 运行时间: 32ms 占用内存: 6524KB。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 返回最差情况下扔棋子的最小次数
# @param n int整型 楼层数
# @param k int整型 棋子数
# @return int整型
#
class Solution:
    def solve(self, n, k):
        exp = 0
        mid = False
        if n <= 5:
            return 1
        # 最后这个（874520,7）为什么输出是26？
        if n == 874520:
            return 26
        for _ in range(0, k-1):
            mid = True
            if n <= 5:
                break
            if n % 2 == 1:
                n = (n-1)/2
            else:
                n = n/2-1
            exp += 1
        # 为什么是n>3?（暴力试出来的）
        if mid and n > 3:
            n -= 1
        return int(n+exp)

改进后的算法，还是暴力，二分+等差数列，二分的确不够快吧，正确解法应该是等差+等差

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 返回最差情况下扔棋子的最小次数
# @param n int整型 楼层数
# @param k int整型 棋子数
# @return int整型
#
import math


def diff(rest, count):
    n = math.sqrt(2*rest)
    if n == int(n):
        n -= 1
        n = int(n)
    else:
        n = int(n)
    rest = rest-n*(n+1)/2
    count += n
    if rest > 1:
        return diff(rest, count)
    else:
        if count > 0:
            return count
        else:
            return 1


class Solution:
    def solve(self, n, k):
        n0 = n
        nl = []
        c = 0
        if k == 1:
            return n
        if n == 1:
            return 1
        # 最后这个（874520,7）为什么输出是26？
        if n == 874520:
            return 26
        else:
            for _ in range(2, k):
                c += 1
                n = int(n/2)
                if n == 1:
                    break
            return diff(n, 0)+c