首页 > 代码库 > HDOJ 4430 Yukari's Birthday 【枚举】+【二分】
HDOJ 4430 Yukari's Birthday 【枚举】+【二分】
题意:有一个蛋糕,将所有的蜡烛摆成一个以中心为同心轴的同心圆(中心可以放一个或者一个也不放,由近到远编号(1~r)每一个圆上分别放k^i(i是第几个的序号, k》=2)), 给你总的蜡烛数,让你求出k*r最小的,如果k*r相等,取r较小的。
分析:由等比数列可得k^0+k^1+。。。+k^r = (1-k^(r+1))/(1-k) 小于等于10e12,k最小是2,算出来r《40,那么我们可以枚举r,然后二分查找k,但是如果按照正常的二分,TL了(6s都TL。。。),分析发现,算幂的时候可能会溢出(64位也会溢出),当我们算到k^i < n如果溢出的话肯定有k^i>n =>k^(i-1)*k>n => n/k^(i-1) < k 这样就可以防止溢出了。
而且,计算得每一个对于每一个r要想k^r<=n k最大等于pow(n, 1.0/r)(仔细想一下)。
代码(200+):
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define LL __int64 #define M 100000 struct node{ LL r, k, j; }s[M]; LL tot, n; bool cmp(node a, node b){ if(a.j == b.j) return a.r<b.r; return a.j<b.j; } void solve(){ LL i, left, right, mid, sum; for(i = 1; i < 45; i ++){ left = 2; right = pow(n, 1.0/i); //这里可以换成n,我的运行时间是800+ while(left <= right){ sum = 0; LL temp = 1; mid = (left+right)>>1; for(LL j = 1; j <= i; j ++){ if(n/temp < mid){ // sum = n+1; break; } temp *= mid; sum += temp; } if(sum == n||sum == n-1){ s[tot].k = mid; s[tot].r = i; s[tot++].j = mid + i; break; } else if(sum < 0||sum> n) right = mid-1; else left = mid+1; } } } int main(){ while(~scanf("%I64d", &n)){ tot = 0; solve(); sort(s, s+tot, cmp); printf("%I64d %I64d\n", s[0].r, s[0].k); } return 0; }题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4430
HDOJ 4430 Yukari's Birthday 【枚举】+【二分】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。