巧克力装包问题：二分答案与贪心算法

问题描述：

有n个巧克力，每个巧克力都是厚度一样的正方形巧克力板，边长分别为a1,a2...an，认为第i个巧克力的重量为ai²。

第一行输入两个整数n和m，表示巧克力数量和小美询问数量。

第二行n个整数a1,a2..an表示n块正方形巧克力板的边长,注意不能将巧克力板进行拆分，

第三行m个整数q1,q2...qn第i个整数qi表示询问：如果小美选择一个能装qi重量的钱包，最多能装多少巧克力板？

1<=n,m<=50000，1<=ai<=10四次方,1<=qi<=10十八次方

输出：

输出一行m个整数，表示每次询问的答案

思路：

考虑用二分答案来解决这个问题。对于每个询问 q_i，我们二分一个最大的 k，使得能够选出 k 块巧克力板，使得它们的重量不超过 q_i。如果能选出 k 块巧克力板，那么一定也能选出 k-1 块巧克力板。因此，我们可以用二分答案，找到最大的 k，使得能够选出 k 块巧克力板，而不能选出 k+1 块巧克力板。

对于每个 k，我们可以用贪心的策略来选出 k 块巧克力板：我们先将巧克力板按照重量从大到小排序，然后依次选取重量最大的巧克力板，直到选出 k 块巧克力板或者所有的巧克力板都被选完为止。

时间复杂度：

O(m log^2 n)

代码：

# 这里省略代码，具体代码实现请参考相关算法教程