题目链接
https://codeforces.com/contest/520/problem/B
题目描述
输入两个不同的整数n m,范围都在[1, 1e4]. 每次操作,可以将n*=2,或者n-=1,至少操作多少次可以得到m。
样例
1.iuput
4 6
1.output
2
2.iuput
10 1
2.output
9
算法1
(暴力dp) $O(n^2)$
dp的思想和acwing的这道题有点像,加减乘,不同的是acwing的这道题起点一定是0,但是这道题的起点不一定是0。但是我们发现这道题的时间限制是2s,所以我们可以写一个两重循环,保证大于n和小于n的点都能充分被更新。
这种做法的好处是代码简单,好想,但是缺点就是时间复杂度太大,如果时间缩短成了一秒,就会TLE。
C++ 代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int N = 1e4+10;
int n, m;
int w[N];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n>>m;
memset(w, 0x3f, sizeof w);
w[n] = 0;
for(int j=0;j<N;j++)
{
for(int i=1;i<N;i++)
{
if(i*2<N) w[i*2]=min(w[i]+1, w[i*2]);
if(i<N-1) w[i]=min(w[i], w[i+1]+1);
}
}
cout<<w[m]<<endl;
return 0;
}
算法2
(找规律) $O(log(n))$
我们发现,如果m<=n时,最优方法是n只能通过减一来变到m,不能有乘以2的操作,一旦乘以了2,操作数量一定会变大。
那么当m>n时,我们可以反过来考虑,如何从m变到n,那么操作就变成了每次除以2(当前数是偶数的情况下),或者加上1。我们只需要在m>n的情况下,如果m为奇数,就先加1,再除以2;如果m为偶数,就直接除以2,直到m<=n。再让m不停地加1直到与n相等即可。下证为什么一直让m除以2,尽量不要加1,除非当前m为奇数。
假设m为偶数(奇数也是一样的证明),每次让m加上2再除以2,和直接让m除以2再加1的结果是一样的,但是前者的操作次数是3,后者的操作次数是2,说明操作2优于操作1。
假设m在区间($2^k*n$, $2^{k+1}*n$]内,可以把m拆分为$2^k*n+z$。这样拆分区间的原因是每次m除以2,都一定会跳掉上一个区间。如果z等于0,那么我们只要不停地除以2就好了,最后会直接等于n;如果z不为0,我们每次在除以2之前一定不会一直加,把m加到超出$2^{k+1}*n$,因为超出后m除以2还是在这个区间,但是我们需要让m跳掉上一个区间。我们可以发现z的取值范围一直小于当前区间的长度,假设按上述算法最后m变成了n-y,那么我们最后只需额外在加上y个1就好了,除去必须加1和除2的操作外操作数为y。若我们在整个过程中加了x个1(除去因为m是奇数必须加一的数量),x一定为偶数(不然不能整除2),那么m最后变成了n-y+x/2,最后还需加上(y-x/2)个1,但是中途还需要x次操作加1,所以除去必须加1和除2的操作外还要y+x/2此操作,这比不额外加1的操作数多。证毕。
C++ 代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5+10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
int res = 0;
if(m<=n) res = n - m;
else{
while(m>n){
if(m % 2) m++, res++; // 如果m是奇数
m /= 2, res++; // 将m整除2
}
while(m<n) res++, m++;
}
cout<<res<<endl;
return 0;
}
算法3
(二进制) $O(1)$
如果m<=n,我们还是直接得出答案即可。当m>n时,m的二进制位数一定大于n我们可以将n的位数将m分为两个部分,前部分拿到m的开头长度与n一样的二进制数start,后部分拿到m剩余的数end,我们还是可以这样考虑:每次将m除以2或者加1。end就是每次除以2消去的,在二进制下就是每次将数字向右移一位,结果会先加上n-start,这个是每次加1的次数,再加上end的长度,这个是每次除以2的次数,如果end不为0的话,我们在遇到end的结尾为1时,需要先加上1在除以2,所以在加上加1的次数,并且start++,因为不停地加1,最终一定会加到start里。如果发现start是大于n的话,表示这种情况是不成立的,需要将start的位数减1,再重复计算一遍即可,这时是一定成立的,因为n比start多了一位,即使start+1,也不会超过n。
那为什么不直接计算第二种情况,反正它始终成立,而是要先看一下第一种情况呢?这时因为在第二种情况下,end不仅要多移一位,start也会更小于n,变化的次数会更多,所以先考虑第一种情况。
C++ 代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int N = 1e7+10;
int n, m;
int x, y;
LL f[N];
int get_0_b(int x) // 返回32位下x的前导0 比如101001 返回16
{
int res = 0;
for(int i=31;~i;i--){
if((x>>i&1)==0) res++;
else break;
}
return res;
}
int get_1(int x) // 返回x的二进制中有多少位数是1,比如01011 返回3
{
int res = 0;
for(int i=0;i<32;i++) res += x>>i&1;
return res;
}
int get_0_e(int x) // 返回x有多少的后缀零 比如1001001000 返回3, 1001010 返回1
{
int res = 0;
for(int i=0;i<32;i++){
if((x>>i&1)==0) res++;
else break;
}
return res;
}
void solve()
{
cin>>n>>m;
if(m<=n){
cout<<n-m<<endl;
return;
}
int a = 32 - get_0_b(n), b = 32 - get_0_b(m);
if(b>a){
int deta = b - a;
int start = m >> deta;
int end = m & ((1<<deta) - 1);
int res = n - start + deta;
if(end){
start++;
res += deta - get_1(end) - get_0_e(end);
}
if(start <= n){
cout<<res<<endl;
return;
}
}
int deta = b - a + 1;
int start = m >> deta;
int end = m & ((1<<deta) - 1);
int res = n - start + deta;
if(end) res += deta - get_1(end) - get_0_e(end);
cout<<res<<endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
solve();
return 0;
}
逻辑清晰,语言流畅连贯,可惜听不懂