例1
关于从长方形的巧克力中切出正方形的小巧克力，可以看下面的示意图：
上图是一块5x6的巧克力分别切出1x1、2x2和3x3的示意图。切成1x1一共可以切出30块，切成2x2可以切出6块。四个1是一块，四个2是一块，以此类推。切成3x3一共可以切出2块。用公式来说的话，一块HxW的巧克力，如果要切出边长是x的正方形，一共可以切出$\lfloor \frac{H}{x} \rfloor \times \lfloor \frac{W}{x} \rfloor$块正方形的巧克力
现在题目的要求是，在保证至少切出K块正方形巧克力的前提下，要正方形的边长越大越好。首先我们应该很容易想到，正方形的边长越大，能切出来的数量就越少
比如我们看样例是一块5x6的巧克力和一块6x5的巧克力。如果边长是1，那么一共可以切出来30+30=60块；如果边长是2，那么一共可以切出来6+6=12块；如果边长是3，那么一共可以切出来2+2=4块；如果边长是4，那么一共可以切出来1+1=2块。如果边长是5，那么也是2块。
因为题目要求至少保证10块，所以答案就是2。因为边长是2可以切出12块；而再大一点边长是3的话就只能切出6块了。
思路1 暴力枚举
从小到大枚举边长x；对于确定的x，计算N块巧克力一共能切出多少边长为x的正方形；如果数量大于等于K，记录当前的x作为答案；否则说明边长x已经过大，直接退出枚举。伪代码如下：
For X = 1...100000
Cnt = 0
For i = 1...N
Cnt += (H[i]/x)*(w[i]/x)
If(cnt >= x)
Ans = x
else
break
print Ans上面枚举边长x的复杂度是$O(Ans)$，然后枚举所有的巧克力，计算能切出的正方形数量，复杂度是$O(N)$，所以整个程序的时间复杂度是$O(Ans*N)$，根据题目给的数据范围，很有可能会超时
优化
假设有一个数组a[1], a[2], a[3], … a[100000]。其中a[i]的值是当x=i的时候，总共能切出来的正方形数目。我们现在并不知道每一个a[i]的值是多少，但是我们知道可以用一个函数f(i)求出来，并且f(i)的时间复杂度是$O(N)$。其次，我们还知道一个重要信息，a数组是递减的，a[i]一定大于等于a[i+1]
而我们的目标是找到最大的边长x，实际上就是找到a数组中，值大于等于K，并且下标最大的这个下标。我们可以发现这个描述和我们之前的求lower_bound很类似。实际上如果我们想象一下把a数组首尾颠倒一下，其实就是在颠倒的a数组里求lower_bound(K)。虽然我们现在面对的a数组是递减的，不是递增的，但是一样可以用二分查找求解。代码如下：
#include <iostream>
using namespace std;
int n,k,h[100010],w[100010];
bool ok(int m)
{
long long c = 0;
for(int i = 0;i < n;i++)
c += (long long)(h[i] / m) * (w[i] / m);
if(c >= k)
return true;
return false;
}
int main()
{
cin >> n >> k;
for(int i = 0;i < n;i++)
cin >> h[i] >> w[i];
int ans = 1;
int l = 1,r = 100000;
while(l <= r)
{
int m = l + (r - l) / 2;
if(ok(m))
{
ans = m;
l = m + 1;
}
else
r = m - 1;
}
cout << ans;
return 0;
}第9~11行是在判断假如切出来的正方形边长为m，数量够不够k，如果够就返回ture，否则返回false
如果ok(m)的返回值是true，说明当前边长m满足条件，就先记下来作为答案ans；边长是m满足条件，那么边长是l~m-1一定也都满足条件，所以我们只需要再尝试m+1, m+2, .. r。于是第24行我们令l=m+1
例2 题目链接：hihoCoder1357
小Ho的城市有K层护盾，每层护盾能抵挡M点伤害。受了伤但是还没被打爆的护盾可以“回血”，每秒回一点。同时小Hi有N枚炮弹，第i枚会造成Ai点伤害。小Hi会按顺序用N枚炮弹去攻击小Ho的城市，攻击的间隔是T秒。所以小Ho的护盾如果没被上一发打爆的话，就可以在这T秒内回血。
显然攻击间隔越小，小Ho撑过N次攻击的可能性越小。问要满足小Ho的K层护盾没有被全部打爆，攻击间隔最小可能是多少
先我们分析一下题目就可以知道。假如攻击间隔T是确定的，那么整个攻击/回血的过程就确定了，换句话说小Ho的K层护盾会不会被打爆就是确定的。所以我们可以先实现一个bool crash(int t)函数，表示当攻击间隔是t秒时，小Ho会不会被打爆。伪代码如下：
Bool crash(t)
C = m,Cnt = 0//C是当前护盾HP，Cnt是击穿了基层护盾
For i = 1...N
If A[i] >= C//第i枚炮弹击穿当前护盾
Cnt++
C = m
Else
C = min(m,C-A[i]+t)
return Cnt >= k//如果击穿k层护盾就返回true此外，题目描述中也暗示了，攻击间隔越小，护盾越容易被打爆。所以如果我们假设有一个数组，a[1]=crash(1)， a[2]=crash(2), a[3]=crash(3) … 显然这个数组不会FALSE排在TRUE前面。换言之，从某种意义上讲也是有序的。而我们现在要在a数组里找值是FALSE的元素中下标最小的元素的下标。显然是可以二分查找的。代码如下：
#include <iostream>
using namespace std;
int n,k,m,a[100000];
bool crash(int t)
{
int c = m,cnt = 0;
for(int i = 0;i < n;i++)
{
if(a[i] >= c)
{
cnt++;
c = m;
}
else
{
c = c - a[i] + t;
if(c > m)
c = m;
}
}
return cnt >= k;
}
int main()
{
cin >> n >> m >> k;
int count = 0;
for(int i = 0;i < n;i++)
{
cin >> a[i];
if(a[i] >= m)
count++;
}
if(count >= k)
{
cout << -1 << endl;
return 0;
}
int l = 1,r = m;
int ans = m;
while(l <= r)
{
int t = l + (r - l) / 2;
if(crash(t))
l = t + 1;
else
{
ans = t;
r = t - 1;
}
}
cout << ans << endl;
return 0;
}注意第33~37行，这是在特判一种情况。假如无论攻击间隔多大，小Ho的护盾都必定被打爆，那么就输出-1。如果不是这种情况，那么crash(M)的值一定是FALSE。因为攻击间隔M秒会使得只要没有一发击穿护盾，残血护盾就一定能回满
所以攻击间隔枚举的范围就是1-M，并且先把ans的初始值设为M。第40~50行就是在二分查找，t是范围[l, r]的中点。如果crash(t)的值是TRUE，说明间隔t秒被打爆了，所以要继续尝试比t更大的攻击间隔；否则说明间隔t秒能抗住，那就先把t记作答案，然后再尝试比t更小的攻击间隔
