[cf]287B Pipeline【二分】

1、二分思想主要是用来加速线性尝试查找

2、至于具体问题，改变的主要是judge函数的问题；二分边界的话考虑清楚一次就可以了。*

3、遇到两个阻碍：一是推公式：等差数列公差是-1而不是1。。水管的接法——总要耗费一个接头用来接自己；

二是数据容量**：long long不是一路用下来的话可能遭遇强转，最后的long long也是没用的。。

4、不要把debug的输出交上去啊啊啊。。。sigh

*关于右边界的问题：这道题算是幸运啊，实际上是不允许使用k个splitter的，只不过由于公式结构、最后加的1同时又被减去了，所以对结果没有影响。但就二分而言，这样写右边界石闭的。将右边界改为k-1更正确。

**主要是int的表达式算出来之后仍是int 待到赋给long long时才强转。

editedversion：

//Pipeline 2013.7.22
#include <iostream>
#include <cstdlib>

using namespace std;
long long n;
int k;

bool judge(int mid)
{
 if(n==1 && mid>-1) return true;
 long long m = (long long)mid;
 long long sum = 1+(2*(long long)k - (m - 1))*m/2-m;
 //cout<<"sum = "<<sum<<" while n = "<<n<<endl;
 return sum >= n;
}

int main()
{
 cin>>n>>k;
 int l = 0,r = k-1,mid,res = -1;
 while(l<=r)//[l,r)
 {
 mid = l + (r-l)/2;//avoid overflow
 //cout<<"mid = "<<mid<<endl;
 bool ans = judge(mid);
 //cout<<"ans = "<<ans<<endl;
 if(ans)
 {
 r = mid - 1;
 res = mid;
 //cout<<"res = "<<res<<endl;
 }
 else
 {
 l = mid + 1;
 }
 }
 cout<<res<<endl;

 return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!