(CF520B)Two Buttons

原题链接

思路:

贪心

\(m\) 为偶数,则将 \(n\) 变为 \(m/2\), 否则变为 \(\(m+1\)/2\), 然后递归求解

下面简单说明为何这个方案是最优方案:

假设 \(n > \frac{m}{2}\), 且 \(m\) 为偶数,有两种方案将 n 变为 m:

  1. \(n*2\), 然后减到 m

  2. \(n\) 减到 \(\frac{m}{2}\), 然后乘 2

假设 \(n = \frac{m}{2} + x\), 则:

方案 1 所需步骤为 \(2x+1\)

方案 2 所需步骤为 \(x+1\)

显然方案 2 更优.

\(m\) 为奇数,则将上面的 \(m\) 改为 \(m+1\), 同样能得到方案 2 更优的结果

\(n < \frac{m}{2}\), 则将 \(m\) 变为 \(\frac{m}{2}\), 可使得每次的 \(x\) 最小

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>

int main()
{
int n,m;
scanf("%d %d",&n,&m);
int ans(0); //答案
while(n!=m)
{
if(m<n)
{
ans += n-m; //如果n大于m只能进行减操作
m=n;
}
else
{
if(m%2) ++m; //将m变为m+1
else m /= 2; //m递归(推)除2
++ans;
}
}
printf("%d",ans);
return 0;
}