有n个巧克力每个巧克力都是厚度一样的正方形巧克力板边长分别为a1a2an认为第i个巧克力的重量为ai²。第一行输入两个整数n和m表示巧克力数量和小美询问数量。第二行n个整数a1a2an表示n块正方形巧克力板的边长注意不能将巧克力板进行拆分第三行m个整数q1q2qn第i个整数qi表示询问：如果小美选择一个能装qi重量的钱包最多能装多少巧克力板？1=nm=500001=ai=10四次方1=qi=10十八次方输出一行m个整数表示每次询问的答案用c++实现

思路：二分答案+前缀和

首先我们可以发现，如果小美选择的钱包能装下x块巧克力板，那么一定能装下1~x块巧克力板，因此我们可以二分答案x，然后判断能否将前x块巧克力板放入小美的钱包中。

具体实现中，我们可以先将巧克力板按重量从小到大排序，然后用前缀和维护前i块巧克力板的重量和，这样就可以O(1)得到前i块巧克力板的重量。

在判断能否放入小美的钱包时，我们可以用双指针维护一个区间，使得这个区间内的巧克力板的重量和不超过小美的钱包能装的重量。具体的，我们可以先将左指针和右指针都指向1，然后不断地将右指针向右移动，直到区间内的巧克力板的重量和超过了小美的钱包能装的重量，此时我们再将左指针向右移动，直到区间内的巧克力板的重量和不超过小美的钱包能装的重量，然后记录区间长度，并将右指针向右移动一个位置，继续寻找下一个区间。

最后，我们将所有能装下的巧克力板数目的最大值作为答案即可。

时间复杂度：排序的复杂度为O(nlogn)，二分答案的复杂度为O(mlogn)，双指针的复杂度为O(n)，因此总的时间复杂度为O(nlogn+mlogn+n)=O((m+n)logn)。

代码实现：