作为一个才开始写代码一周的人
想问一下我这个二分法为何计算不出来
谢谢
```cpp
#include <iostream>
#include <cmath>
using namespace std;
double mlog(int,int);
int main()
{ int a,b;
cin >> a >> b;
if (a<=0||a==1||b<=0)
{
cout << "输入错误" ; //检测输入是否正确
}
else
{
cout << mlog(a,b);
}
}
double mlog(int,int) //x是底数,y是真数,比较pow(x,z)与y的距离
{ double x,y;
cin >> x >> y;
double k=0; //m,n为值,k为常数
double m,n;
while ((m-y)*(n-y)>0)
{ m=pow(x,k);
n=pow(x,k+1);
k=k+1;
} //求出区间【k,k+1】
double l,r; //设置左端点和右端点
l=k;
r=k+1;
while (n-y>=0.0001)
{ m=pow(x,l);
n=pow(x,r);
if (y<pow(x,(l+r)/2))
r=(l+r)/2;
if (y>pow(x,(l+r)/2))
l=(l+r)/2;
}
return l;
}
```
by Alessandro @ 2017-09-20 20:50:36
不用判断输入错误的啦~
还有用不着这么多的double啦~
不管是哪道题,我有个标准二分模板,推荐你试一试:
```cpp
while (l<=r)
{
mid=(l+r)>>1;
if (……)mid=l+1;
else r=mid-1;
}
看看你的二分有没有错~然后,这不是这道题的二分吧~你可以去学术区啊~
by vani_prcups @ 2017-09-20 21:25:01
@[Alessandro](/space/show?uid=57594)
by vani_prcups @ 2017-09-20 21:26:06
楼主是想到了和导弹拦截一样的单调队列n log n吗。。
应该是有的吧
一个队列queue[x]表示长度为x的下降子序列最后一个数的编号,由于编号有多种,用数组存储(因为要记录方案数,不然就只要和导弹拦截一样记一个最大高度即可),并且记录这么多编号中价格最大的一个,根据这个最大的价格进行二分,然后把第i个数挂进该挂的地方queue[t],判断一下i的价格是否是t这个位置上的最大价格,是就更新,不是就只是挂在那里;然后计算方案数。。。。
orz应该比n log n稍微多一点 因为有方案数这个神奇的东西……
我就瞎猜一下……第一遍看题的时候我也想写n log n来着 因为太麻烦了就没把上面那个写出来,所以并不知道对不对……
by 上天台 @ 2017-09-24 13:23:09
刚刚去看了那个传说中用栈n log n的题解,发现我可能理解错了楼主的意思……
我错了QAQ
我瞎猜的n log n和题解的那个其实一模一样……只不过我写队列他写栈而已orz
题解那个就是二分查找,只不过查找的是队列里的元素而已……其实这个写法和栈的性质没关系的,重点在于单调性和二分
于是我猜楼主可能是想说二分答案…… 二分答案大概可能也许不存在吧OTZ 如果是子串倒是可以二分 然而也许会有神犇提出来某些神奇的做法也不一定
猜错了意思的蒟蒻遁走了……
by 上天台 @ 2017-09-24 13:45:02
@[prcups](/space/show?uid=33930) 谢谢!
by Alessandro @ 2017-09-30 21:09:07