题解 P1582 【倒水】

shenbear · 2019-06-19 10:35:15 · 题解

这道题的本质就是将n转为二进制后找到一个比它大且1的数量<=k的二进制数,然后再用此数-n

各位大佬好像都是用二进制做的,我也是,好巧

但是二进制具体如何实现上有点区别

至于为什么是二进制,楼上楼下的各位大佬已经讲的很清楚了,我就不重复了

重点讲如何实现

首先当然要先把n化为二进制,长度为l

然后去找,在前k个一中的最后一个为0的位置

如果不存在,则直接用2^(l+1)-n(前面无论怎么将1改0都没用,必须多加一位,才能使1的数量<=k

如果找到了,那就把这位变成1,后面全改为0,再拿此数去-n

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x,n,k,a[111],l=-1,s;
ll pw(int b,int c) //建议手写pow
{
    ll sum=1;
    for(int i=1;i<=c;i++)
    {
        sum*=b;
    }
    return sum;
}
ll check()
{
    ll zz=-100;
    for(int i=l,j=1;j<=k;i--)//找位置
    {
        if(!a[i]) 
        {
            zz=i;
            //return zz;
        }
        else j++;
    }
    if(zz==-100)
    return 0;
    else return zz;
}
int main()
{
    cin>>n>>k;
    x=n;
    while(x)//转二进制
    {
        l++;
        s+=x%2;
        a[l]=x%2;
        x/=2;
    }
   if(s<=k)//根本不用做的
   {
       cout<<"0";
       return 0;
   }
   //cout<<check();
   ll z=check();
    if(!z) //没有找到
    {
        cout<<pw(2,l+1)-n;
    }
    else //找到了
    {

        a[z]=1;
        ll sum=0;
        for(int i=z;i<=l;i++)
        {
            sum+=pw(2,i)*a[i];
        }
    //    cout<<sum<<endl;
        cout<<sum-n;
    }

}