题意:有n支蜡烛,要插成r圈,第i圈的数量为k^i个,中间可插可不插,求出r*k的最小值,相同时去r最小。
思路:当时加这个比赛时我们已经把思路想出来了,没看到中间可以不插蜡烛。最多不超过四十圈,所以枚举圈数,然后二分找k,因为是一圈的时候一定是1,n-1,所以从2开始枚举。k有个上限就是1000000。
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; typedef long long LL; LL find(int x,LL N) { LL L,R,mid,bt,sum; L=2;R=1000000; while(L<=R) { mid=(L+R)>>1; sum=0;bt=1; for(int i=1;i<=x;i++) { bt*=mid; sum+=bt; if(sum>N)break; } if(sum>N) { R=mid-1; } else if(sum==N)return mid; else L=mid+1; } return -1; } int main() { int i; LL r,k,f1,f2,n; while(scanf("%lld",&n)!=-1) { r=1;k=n-1; for(i=2;i<40;i++) { f1=find(i,n); f2=find(i,n-1); if(f1!=-1) { if(f1*i<r*k) r=i,k=f1; else if(f1*i==r*k&&i<r) r=i,k=f1; } if(f2!=-1) { if(f2*i<r*k) r=i,k=f2; else if(f2*i==r*k&&i<r) r=i,k=f2; } } printf("%lld %lld\n",r,k); } return 0; }