二分搜索 UVALive 6076 Yukari's Birthday (12长春K)-白红宇

二分搜索 UVALive 6076 Yukari's Birthday (12长春K)

阅读量：6038 次

发布时间：2019-06-20

本文共 1684 字，大约阅读时间需要 5 分钟。

题意：问使得sum (k^i) = n || n -1 (1 <= i <= r) 的min (r*k)组合的r和k

分析：r的最大不会超过40，枚举r，二分搜索k。注意会爆long long，所以上界需要优化。r = 2开始上界就小于1e6，cyd将后面的范围也求出来了，其实1e6就够用了。

这水题卡了我好久，没有很好分析题目，做不出来就有种无力感，开始烦躁起来。还是题目做得少了，如果这种题做多了，可能看一眼就能做出来了。

/************************************************* Author        :Running_Time* Created Time  :2010-1-16 12:18:59* File Name     :K.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-10;const double PI = acos (-1.0);ll n, r, k;ll cal(ll x, int y) { ll ret = 0, p = x; for (int i=1; i<=y; ++i) { ret = ret + p; p *= x; if (ret > (ll)1e12) return ret; } return ret;}ll bsearch(ll l, ll r, int m, ll ans) { while (l <= r) { ll mid = (l + r) >> 1; ll sum = cal (mid, m); if (sum == ans) return mid; else if (sum < ans) l = mid + 1; else r = mid - 1; } return 0;}int main(void) { while (scanf ("%lld", &n) == 1) { r = 1; k = n - 1; ll kk; for (int i=2; i<=40; ++i) { kk = bsearch (2, 1e6, i, n); if (kk == 0) continue; if (1ll * i * kk < r * k) { r = i; k = kk; } } for (int i=2; i<=40; ++i) { kk = bsearch (2, 1e6, i, n - 1); if (kk == 0) continue; if (1ll * i * kk < r * k) { r = i; k = kk; } } printf ("%lld %lld\n", r, k); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4918343.html

你可能感兴趣的文章