直接按照题目意思模拟即可
可以递推或者公式求出每个h对应的cost
然后每次使用剩余的n,找到最大的cost<=n
这个找的过程,第一次用的二分,超时了,可能是因为答案多为h较小的cost
第二次用解方程,然后左右移动寻找精准的h,也超时了
根据代码也许是sqrt()函数的复杂度过高?
于是阅读了(8条消息) sqrt方法复杂度探讨_Jiewang的博客-CSDN博客_sqrt 时间复杂度
记录下【牛顿下降法】
牛顿下降法的原理为:
求根号a的近似值,相当于求f(x) = x^2-a的解。
首先随便猜一个近似值x,然后不断令x等于x和a/x的平均数,迭代个六七次后x的值就已经相当精确了。
这种算法的原理很简单:
仅仅是不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根,这个函数的导数是2x。也就是说,函数上任一点(x,f(x))处的切线斜率是2x。那么,设下一轮迭代新解为k,直线的等式为:(x-k)*2x =f(x),k=x-f(x)/(2x)就是一个比x更接近的近似值。代入f(x)=x^2-a得到k = x-(x^2-a)/(2x),也就是k = (x+a/x)/2。
关于【sqrt的时间复杂度 】
来自C库函数log、sqrt的时间复杂度是多少?-CSDN社区
sqrt log 这样的函数,都是调用相应的CPU指令,也就是说函数本身不作数值运算。
在intel 的CPU手册上可以看到,这些初等函数消耗的CPU周期都是有一个范围的。所以
这些函数可以当成常数复杂度来看待。这些函数所消耗的时间和你的问题的规模没关系。
这之后直接试了下枚举,反而过了,还好没接着尝试记忆化...
#include<cstdio> #include<cstdlib> #include<iostream> #include<cmath> using namespace std; int T; inline int read() { int x=0;char c=getchar(); while(c<'0' || c>'9' ) c=getchar(); while(c>='0'&&c<='9' ) x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x; } int n,m; const int N=3e5+10; int Cos[N]; void prepare() { for(int i=1;i<26000;i++) Cos[i]=(3*i+1)*i/2; } int get(int v) { // int t=sqrt(v*3/2); // while(Cos[t+1]<=v ) t++; // while(Cos[t]>v ) t--; // return t; for(int i=0;i<=N;i++) if(Cos[i]<=v && Cos[i+1]>v ) return i; //二分或者直接计算,都不如枚举 为什么? } int main() { prepare(); T=read(); while(T--) { n=read(); int ans=0,pos=n; while(n>0) { pos=get(n); if(!pos ) break; else { n-=Cos[pos]; ans++; } } printf("%d\n",ans); } return 0; }View Code