c++ 二分答案

2019-07-14

c++ 二分答案

问题

使得x^x达到或超过n位数字的最小正整数x是多少?n<=2000000000

分析

对与这种较难求解的问题,我们很难想出较好的解决策略。但是,我们至少知道答案一定在1与2000000000之间,能否转换二分查找的思想,对答案进行二分查找呢?当然是可以的,但在二分查找中有比较,在二分答案中,我们也需要有比较,我们用检查函数来实现。如果检查出的是一个合法的解,那么我们尝试找更优的解,如果检查出的是不合法的解,我们尝试找合法的解,这就是二分答案的思想。在这题中,我们设计的检查函数就是x^x的数位是否超过n位,合法返回真,不合法返回假。再二分求解即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
int o;
bool check(int k)//查看这个数的位数 
{
    long long p = k;
    return p * log10(1.0*k) + 1 >= o;//判断数位的公式 
}
int medium()
{
    int l = 0;//确保范围在 l 和 r 之间  
    int r = 2000000000;
    while (l + 1 < r)//确保不越界(l < r) 
    {
        int mid = (l + r) / 2;
        if (check(mid))//如果这个解满足要求 
        {
            r = mid;//缩小范围 
        }
        else//如果这个解不满足要求 
        {
            l = mid;//继续在右半部分寻找解  
        }
    }
    if (check(l))//如果解合法 
    {
        return l;
    }
    else//不合法 
    {
        return r;
    }
}
int main()
{
    cin >> o;
    cout << medium() << endl;
    return 0;
}

备注:
公式推导: