115.公平

题目概述

题目详情(点我)

到了万圣节，Tom要给小朋友们发糖，现在有两个小朋友，他们手里分别有x个糖和y个糖(1<=x,y<=1e9)，但是糖少的小朋友就会不开心，Tom想让他们两个的糖一样多。Tom的操作是这样的，第一次给他们其中一个小朋友发一个糖，第二次给他们其中一个小朋友两个糖，第三次给他们其中一个小朋友发三个糖，以此类推，问至少要多少次这两个小朋友的糖会变的一样多。

输入两个数字，输入x和y，表示两个小朋友刚开始所拥有的糖数。
输出Tom要发多少次使得两个小朋友的糖一样多。

题解

解题方法

• 找规律

算法知识

• 枚举法

  • 时间复杂度: n
  • 空间复杂度: 1

解题思路

前提:
int x[0], x[1] ： 代表两个小朋友, x[0] + x[1] = 总糖数
int i : 变量，代表每次发糖的粒数; 每发一次, i+1

1. 比较 x[0], x[1] 当前有的糖, 并让 x[0] 小朋友的糖少于 x[1] 小朋友。(此步骤为了确认后面到底是要给哪个小朋友糖)

2. 给糖少的小朋友 x[0] 发糖 (x[0] + i++), 直到糖少的小朋友 x[0] 的糖 大于或等于 x[1] 的糖。

   • 如果此时 x[0] = x[1], 则直接输出 i-1 即可
     (为什么是 i-1 : 因为前面用的i++, 会导致i的值比实际大1)

3. 剩下的就是 x[0] > x[1] 的情况啦

   • 计算 (x[0] + x[1]) % 2 判断当前总糖数是否能被2整除

     • 如果能, 则输出 i-1
     • 如果不能, 则继续给x[0]发糖 (i就继续加), 直到两数之和能被整除为止, 然后输出 i-1 (为什么呢 (⊙_⊙)？)

• 为什么要判断能否被2整除？

  • 如果两个数相等, 那么这两个数的和一定是偶数（所以能被2整除）
  • 所以如果两个数之和为奇数，那么就得再给一次糖, 让两个数的和为偶数，才能让两个人的糖一样多 (不知道为什么? 往下看)

• 为什么当加到超过x[1]就可以停下了？

  • 如果当 x[0] 小于 x[1] 的时候, 取两个数的和的平均值的话, 则x[1]的值肯定会被减少 (从一个小朋友那里抢糖), 这是题目不允许的。
  • 只有当 x[0] 大于 x[1] 的时候, 两个的数的和的平均值才会提高。

• 为什么 x[0] > x[1] 后, 只需要判断能否被2整除就可以判断糖数是否相等？

  • 直接上图吧
    样例: x[0] = 4; x[1] = 18

• 从样例中可以看出, 只要两数之和为偶数, 就能通过加减i来使得两个数相等。(有疑惑的话自己随便找个示例试试)