题解 | #[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