文章目录
1月11号
1. 解方程1
题目链接
一个非常简单的整数二分问题,如果用暴力时间复杂度是O(n^3)会TLE,所以在我们枚举两个数字后(a,b)后根据已知条件c=-(axx+b*x)然后二分出查找a[]数组中是否存在c,时间复杂度是O(n2logn)
2. 解方程2
解方程2
这是一个分数二分问题,**(2018 * x * x *x * x + 21 * x + 5 * x * x * x + 5 * x * x+ 14==y),给出y让你求x的值为多少.我们从0-100二分查找x,若式子( ** )>=y则更新上界R,看有没有更小的x,反之更新下界L找到更大的x.
3. 圣诞节糖果
圣诞节糖果
预处理+双指针,由于给的糖果大于p会被包装,所以我们对a[]数组进行取模操作,表示我们可以拿走最大的数量.然后我们把a[]进行排序,弄两个指针l和r若a[l]+a[r]>=p则更新上界r,r–反之更新下界l,l++
4.完全平方数
完全平方数
首先我们讲一下数学思路：
因为平方数开了根号之后就是一段连续的数。所以我们对范围开个根号，取中间的整数区间，求出长度就好了：就是sqrt (r ) -sqrt(l)+1。
然后就是二分了：
我们可以先把所有的平方数存起来，然后对左右区间进行二分查找。
二分很方便，我们只要用lower_bound和upper_bound就可以了：就是upper_bound(a,a+n,r) - lower_bound(a,a+n,l)。
5.wyh的物品
01分数规划+二分
这道题要求单位价值（题目中的总价值/总花费），我们假设单位价值为x，我们就可以知道，x = Σv / Σc。
算法分析
我们已经知道了这道题是要二分，那么我们就对单位价值进二分，也就是我们要求的答案。
由上面我们设立的公式：变式可以得到 Σv - Σc * x = 0。我们在二分猜测答案的时候就以这个为基准（为什么呢？看下面）。
如果我们选取的v和c使这个式子>0的话，说明至少还有一组v和c可以使得x更大：Σv - Σc * x > 0。这就是：x < Σv / Σc（算出了答案可以比二分猜测的x大）。
所以我们就可以依照这个式子得到每个物品的权值，然后进行排序，选出最大的k个。进行Σv - Σc * x > 0的判断。
6.小咪买东西
.小咪买东西
同上