ZROI#973

一开始我半天不知道题目让我干什么…

后来才发现他是让我做一个非固定 $k$ 分查找,为什么这么说呢?

因为每次选取的 $k$ 是非固定的.

可以一直一致,也可以是任意一个数字,我们要做的就是每次都选择恰当的 $k$ , 最小化总代价.

显然的一点是 $\forall k,k \ge 2$. 因为你一分查找不能得到任何有效信息,无意义,虽然一分查找不消耗划分价值,但它消耗轮次价值,所以一定不优.

因为有 $\forall k.k \ge 2$ , 所以我们需要进行的轮次至多就是 $\lceil log_2{n}\rceil$.

而 $\lceil log_2{10^9}\rceil$ 不过是 $30$ ,所以直接枚举即可.

那么枚举轮次,怎么去判断/求取答案呢?

先说一个结论,若
$$\prod_{i=1}^m{k_i} \ge n$$
则这个方案一定能找到我们要的元素.

其中, $m$ 是进行的轮次数, $k_i$ 是我们每次选定进行 $k$ 分查找的 $k$.

为什么有这个式子呢?

考虑以二分查找为归纳奠基,调整二分查找进行归纳证明即可.

所以我们得到了判断一组解是否合法的方法.

而我们显然不能枚举每一个 $k$ , 但我们可以枚举 $\sum{k_i}$ , 你可能会问枚举和怎么用上面的式子判断呢?

其实很简单,根据均值不等式,我们可以知道 $\forall i,j$ 一定有 $|k_i-k_j\le 1|$.

因为根据均值不等式,如果 $\exists i,j$ 使得 $k_i-k_j\ge 2$ , 那么令 $k_i$ 变为 $k_i-1$ , $k_j$ 变为 $k_j+1$ 答案一定不会变劣.(考虑我们判断解是否合法的式子)

所以,我们可以枚举轮次数,再去二分 $\sum{k_i}$ , $check$ 的时候根据上面的结论 $check$ , 即均分后,有余数再顺次加上去,做一个乘积,判断合法即可.

注意中间的过程可能会溢出 $long\:long$ , 那怎么办呢?

因为 $n \le 10^9$ ,所以如果溢出则一定合法,直接判断即可.

枚举轮次根据上面的分析,是 $\Theta(log_2{n})$ 的,二分 $\sum{k_i}$ 是 $\Theta(log_2{n})$ 的,而每次的 $check$ 是和轮次数同阶,也是 $\Theta(log_2{n})$ 的,所以总复杂度大概 $\Theta(T\times log_2^3{n})$,其中 $T$ 为数据组数.

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double
#define ull unsigned long long
#define lowbit(x) ( x & ( - x ) )
#define mid ( ( l + r ) >> 1 )

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
       while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
       }
       return f * x ;
    }

const int inf = 1e17 ;

int n , b , a , T , ans ;

inline bool check (int x , int seg) {
    int res = 1 , tmp = x / seg , rem = x % seg ;
    if ( tmp >= n ) return true ;
    rep ( i , 1 , rem ) {
        res *= ( tmp + 1ll ) ;
        if ( res < 0 | res >= n ) return true ;
    }
    rep ( i , rem + 1 , seg ) {
        res *= tmp ;
        if ( res < 0 || res >= n ) return true ;
    }
    return res >= n ;
}

signed main (int argc , char * argv[]) {
    T = rint () ;
    while ( T -- ) {
        ans = inf ; n = rint () ; b = rint () ; a = rint () ;
        if ( n == 1 ) { puts ("0") ; continue ; }
        int flr = ceil ( log2 ( n ) ) ;
        rep ( i , 1 , flr ) {
            int l = 1 , r = n , res = - 1 ;
            while ( l <= r ) {
                if ( check ( mid , i ) ) res = mid , r = mid - 1 ;
                else l = mid + 1 ;
            }
            if ( res == - 1 ) continue ;
            ans = min ( ans , b * i + ( res - i ) * a ) ;
        }
        printf ("%lld\n" , ans ) ;
    }
    system ("pause") ; return 0 ;
}