卡片

::: warning 除了最后一个方法，其他都只能解决70%的实例 :::

动态规划 Link to heading

dp[i]表示当有i个同学时，最少需要多少张卡片
通过思考观察发现：

  • 当i=1时,组合加上(1,1)
  • 当i=2时,组合加上(2,2)
  • 当i=3时,组合加上(2,1)
  • 当i=4时,组合加上(3,3)
  • 当i=5时,组合加上(3,1)
  • 当i=6时,组合加上(3,2)

在1-1时，只需要1张卡片，所以dp[1]=1
在2-3时，只需要2张卡片，所以dp[2]=2
在3-6时，只需要3张卡片，所以dp[6]=3
并且
1张卡片的组合有1种
2张卡片的组合有2种
3张卡片的组合有3种
所以只要i个同学的数量在卡片组合的和范围内就还是需要dp[i]张卡片，否则就需要dp[i-1]+1张卡片

基本代码 Link to heading


n = int(input())
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    if sum(range(1, dp[i-1]+1)) < i:
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = dp[i-1]
print(dp[n])

但是在上方代码中，明显相加和是可以优化的，不必要每一次都计算前方的所有和，而是化成一个变量，循环一次加上一次

优化代码 Link to heading


n = int(input())
dp = [0] * (n + 1)
dp[1] = 1
current_sum = 1
for i in range(2, n + 1):
    if current_sum < i:
        dp[i] = dp[i-1] + 1
        current_sum += dp[i]
    else:
        dp[i] = dp[i-1]
print(dp[n])

数学方法 Link to heading

按照刚才的动态规划思路，其实动态规划也是可以被优化的，因为我们可以发现，每一次的dp[i]都是在dp[i-1]的基础上加1，所以我们可以直接保存一个变量，每次加上1即可

基本代码 Link to heading

n = int(input())
ret = 1
current_sum = 1
for i in range(2, n + 1):
    if current_sum < i:
        ret += 1
        current_sum += ret
print(ret)

优化代码 Link to heading

到了这里不难发现，其实只要组合数的和大于等于n，就可以容纳n个同学的卡片，所以我们可以直接在组合数的和大于等于n时，直接输出i即可

n = int(input())
current_sum = 1
for i in range(2, n + 1):
    current_sum += i
    if current_sum >= n:
        print(i)
        break