二分练习题解

for(int i=1;i<=n;i++){
		if(b[i]<=x){
			y+=(x-b[i])/k[i]+1;
		}
	}

首先第一句话：“第$i$个序列可以表示成$k_i×x+b_i$的形式$（x=0,1,2...）$” 我们得知公式是$k[i]×x+b[i]$，那么我们又得知这个公式后的结果要小于等于$M$才是有效范围，所以就有了$2$种情况，分别是小于等于和大于，那么大于就是一个都没有的情况，序列中最小的数都比这个数大所以就是一个都没有嘛。

那么否则里面有多少个我们对上面的公式做个移项 $k_{[i]}×x \le M-b_{[i]}$。

这时候我们再把$k{[i]}$移过去： $x \le \frac{M-b_[i]}{k_[i]}$

那么具体有多少个那就是$0,1,2$一直到$M-b_[i]÷k[i]$这里是整除$k[i]$，所以具体多少个数我们还需要取下整。 因此最终公式是$x \le \lfloor \frac{M-b_[i]}{k_[i]} \rfloor$，转化成程序就是$(x-b[i])/k[i]+1$。

每一个数列小于等于$M$的数有多少个后，那么一共的话就是把每一组数列中$\le$等于的个数加起来就知道分界线位置是在左边还是右边了。

那么在梳理下这是怎么二分数的呢？ 我们是要这么想，现在要去看看这一个合并完以后的这一个序列里面，小于$1$的，小于等$1$的数有多少个，小于等于$2$的数有多少个，等等等等一直去看小于等于这里面的数有多少个，那么我们小于等于$i$的数有多少个，随着$i$变大，那这样数字个数也会变多，那最后一定能找到一条分界线，对于分界线左边的$x$小于等于$x$的数字有小于$M$个，对于分界线右边的些$x$小于等于$x$的数字有大于等于$M$个，那比如说分界线最后在$L$和$R$之间，那最后$M$小的一定是$R$，那现在我们就是要把分界线，我们去把它二分出来，那分界线怎么二分呢？就是我们二分的时候是吧，我要去看当前小于等于$M$的数字有多少个，那我们就每一个序列，我们每个序列去看过来，看每个序列小于等于$M$有多少个，我把它加起来我就知道了，总共小于等于$M$的有多少个了，对吧？那么这个题的话就是这样的，那么你看一看小于等$M$数字有多少个就可以求出来了。