Happy Birthday！LevOJ P1719 Let's play a game!

思路：遍历每一个Ai，如果Ai=k，则判断此时i是否为2的次幂。

①如果是，则总操作数cnt+1；

②如果不是则要判断i距离前面最近的2次幂的数$2^j$之间的距离。

如果cnt>l，那么一定可以在某一次操作后是的i恰好为2的次幂，此时总操作数cnt+1；

否则总操作数

$ cnt=(i-2^j -cnt)+cnt+1 $

时间复杂度：O(n)

AC代码：

#include<bits/stdc++.h>

using namespace std;

int n,k;

int a[300005];

int main(){
    cin>>n>>k;
    long long cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        if(a[i]!=k){
            continue;
        }else{
            for(int j=0;j<=19;j++){
                if(i==pow(2,j)){
                    cnt++;
                    break;
                }else{
                    if(i>pow(2,j) && i<pow(2,j+1)){
                        if(cnt>(i-pow(2,j))){
                            cnt++;
                        }else{
                            cnt=i-pow(2,j)+1;
                        }
                        break;
                    }
                }
            }
        }
    }
    cout<<cnt<<endl;
}