Binary Search
非常好的博客， http://www.hawstein.com/posts/make-thiner-programming-pearls.html
教你快速读完编程珠玑
round函数 是四舍五入，靠近最近的整数
二分查找专题，瞿神推荐
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=80425#overview
题目B，对于给定数组的m划分，使得每个划分的累加和最大值最小
这里又想了一个计数问题，n个数m划分(要求连续的数划分在一起)，每个至少为1，那么一共多少种。
我进入算法思维，首选dp，对于最后一个元素，所在集合有1个或多个数，因此枚举
dp(n, m)=sum(dp(n-lastsize, m-1)) lastsize=1->n-(m-1)
应该是可以算的。
然而这其实就是一个插板法，n-1块地方放m-1块板，C(n-1,m-1)
言归正传。二分可以考虑二分答案，这是常见思路。对于mid，我们尝试划分
n个数，使得每个区间sum<=mid, 看最后能不能划分m个区间，如果<=m个，说明我们的mid选大了，如果选小一点，区间数可以多一些，以达到刚好m个，但是mid还是要保留，high=mid, 否则low=mid+1.
二分下届是max(ai), 上届是sum(ai)
bool judge(LL mid)
{
LL sum=0, cnt=0;;
for(LL i=0;i<n;i++)
{
sum+=a[i];
if(sum>mid)
{
cnt++;
i--;
sum=0;
}
}
cnt++;
return cnt<=m;
}
int main()
{
/*
#ifndef ONLINE_JUDGE
freopen ("in.txt" , "r" , stdin);
freopen ("out.txt" , "w" , stdout);
#endif
*/
while(cin>>n>>m)
{
LL sum =0, maxx=-1;
for(LL i=0;i<n;i++) cin>>a[i], sum+=a[i] ,maxx=max(maxx, a[i]);
LL low=maxx, high=sum;
while(low<high)
{
LL mid=(low+high)/2;
if(judge(mid)) high=mid;
else low=mid+1;
}
cout<<low<<endl;
}
return 0;
}
另一道更偏数值计算，感觉二分的算法很多是数值计算的内容
里面有一个性质一直没懂
题目E，是01分数规划
max(sum(aixi)/sum(bixi)) st: sum(xi)=n-k, xi=0|1
这个最大值等价于
f(L)=sum(aixi)-L*sum(bixi)
但是具体为何还不清楚。知道这个之后，就是算最大的n-k个ai-mid*bi, 然后
按照这个来二分
double epsilon=1e-7;
while(~scanf("%d%d", &n, &k))
{
if(!n && !k) break;
for(int i=0;i<n;i++) a[i]=getint();
for(int i=0;i<n;i++) b[i]=getint();
double low=0, high=1;
while(high-low>=epsilon)
{
double mid=(low+high)/2;
for(int i=0;i<n;i++) t[i]=a[i]-mid*b[i];
sort(t, t+n);
double f=0;
for(int i=k;i<n;i++) f+=t[i];
if(f>=0) low=mid;
else high=mid;
}
cout<<(round)(low*100)<<endl;
}