题解 | #[USACO 2007 Ope S]Catch That Cow# O(logn)算法
时间复杂度O(logn),空间复杂度O(1)
我们将原问题转换为在指定X*2操作次数计算下X+1和X-1操作的次数;
设X*2次数为opx,计算diff=abs(k*2^opx - n)。通过diff计算X+1和X-1的操作次数。
如果把X+1 X*2看成是X*2 X+2(单个操作加二),那么就可以利用二进制的特性快速求解。
把X+2 X+4 X+8操作简化,可以得到X+16 X-2。只要出现了连续3次或以上操作,我们就把它简化为X+2^a X-2形式。
#include <bits/stdc++.h>
using namespace std;
int nextGELSCount(int a,int b){
int count =0;
while(a<b){
a<<=1;
count++;
}
return count;
}
int maxBit(int a){
int count =0;
while(a){
a>>=1;
count++;
}
return count;
}
int solve(int k,int n){
if(k>=n){
return k-n;
}
int k2 = k;
if(k==0){
k2 = 1;
}
int opx = nextGELSCount(k2,n);
int result = INT32_MAX;
for(int i=0;i<2;i++){
int t1= k2<<opx;
int diff=abs(t1-n);
int state = 0;
int statec = diff / (1<<opx);
int itCount = min(opx,maxBit(diff));
for(int j=0;j<itCount;j++){
if(diff&(1<<j)){
if(state==1){
state = 2;
statec++;
}else if(state ==2){
}else{
state = 1;
statec++;
}
}else{
state = 0;
}
}
if(k==0){
statec++;
}
result = min(result,opx+statec);
if(opx==0)
break;
opx--;
}
return result;
}
int main(){
int k,n;
cin>>k>>n;
cout<<solve(k,n);
}
协议:CC-BY-SA 4.0 作者:sselecirPyM