Leetcode 991. Broken Calculator


题目来源:https://leetcode.com/problems/broken-calculator/description/

标记难度:Medium

提交次数:1/1

代码效率:100.00%(4ms)

题意

给定两个数XY,可以对X执行以下两种操作:

  • 乘2
  • 减1

问最少需要对X执行多少次操作才能将X变成Y?(XY的范围都是1e9)

分析

比赛的时候我居然首先就写了一个BFS,然后自然是超时了……

后来就思考怎么用数学方法解决,也没想出来,各种各样奇怪的贪心大部分也是错的。

后来想到了对X的操作就等同于对Y的除2和加1两种操作,不过想到了也没什么大的突破……

然后就没做出来……


这道题考虑对Y的操作比考虑对X的操作要更容易。如果对Y加1两次再除2,显然不如先除2再加1,因此不会出现两次连续的加1操作。题解[1]是这么说的,不过我感觉有一点不太严谨。倒不如这么说:首先假设有一个最优的操作顺序,需要除2n次,且在第一次除2之前需要加1a[0]次,在第二次除2之前需要加1a[1]次,……,在最后一次除2之后需要加1a[n]次。此时总操作次数为a[0] + a[1] + ... + a[n] + n。假如存在i < na[i] > 1,那显然可以把多余的+1操作下移,变成a'[i] = a[i] - 2 * (a[i]/2)a'[i+1] = a[i+1] + a[i]/2,总操作次数减少a[i]/2次。如果a'[i+1]仍然大于1,则可以继续尝试下移,直到除了a[n]以外的所有a[i]都变成0或1为止。

事实上我大概是做了一个Exchange类型的贪心证明……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int brokenCalc(int X, int Y) {
int ans = 0;
while (Y > X) {
if (Y % 2 == 0) {
Y /= 2;
ans++;
}
else {
Y = (Y + 1) / 2;
ans += 2;
}
}
return ans + (X - Y);
}
};

  1. Leetcode Official Solution for 991. Broken Calculator


 评论