题目描述
Alice 和 Bob 在一个长满鲜花的环形草地玩一个回合制游戏。环形的草地上有一些鲜花,Alice 到 Bob 之间顺时针有 x
朵鲜花,逆时针有 y
朵鲜花。
游戏过程如下:
- Alice 先行动。
- 每一次行动中,当前玩家必须选择顺时针或者逆时针,然后在这个方向上摘一朵鲜花。
- 一次行动结束后,如果所有鲜花都被摘完了,那么 当前 玩家抓住对手并赢得游戏的胜利。
给你两个整数 n
和 m
,你的任务是求出满足以下条件的所有 (x, y)
对:
- 按照上述规则,Alice 必须赢得游戏。
- Alice 顺时针方向上的鲜花数目
x
必须在区间[1,n]
之间。 - Alice 逆时针方向上的鲜花数目
y
必须在区间[1,m]
之间。
请你返回满足题目描述的数对 (x, y)
的数目。
样例
输入:n = 3, m = 2
输出:3
解释:以下数对满足题目要求:(1,2),(3,2),(2,1)。
输入:n = 1, m = 1
输出:0
解释:没有数对满足题目要求。
限制
1 <= n, m <= 10^5
算法
(数学) $O(1)$
- 注意到,当 $x + y$ 为奇数时,Alice 能赢得游戏。
- 两个数字相加为奇数,则必定其中一个数字为奇数,另一个数字为偶数。
- $1$ 到 $n$ 中奇数的个数为 $n - n / 2$,偶数的个数为 $n / 2$。$m$ 同理,直接通过乘法原理和加法原理计算出最终的组合数。
时间复杂度
- 仅需要常数的时间。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
LL flowerGame(int n, int m) {
return (LL)(n - n / 2) * (m / 2) + (LL)(n / 2) * (m - m / 2);
}
};
大佬最近又打周赛了,leetcode究极班就一直看你,坚持这么多年
很久不打了,都是抽空刷一下上周周赛的题