此题非常像中学时代的线性规划。我们通过三个方程在二维坐标上的区域,可以发现第三个条件完全包含在前两个里,可以不用考虑。
一个常规的方法是,遍历每个元素作为A来考虑,然后计算B的取值范围(上下界),然后用二分法在数组中找出上下界的位置,就能得到符合要求的B的个数。这是O(NlogN)的解法,N是元素的个数。
这里推荐另外一种更好的解法。因为元素的范围是固定的1-120,所以我们开辟一个含120个元素的数组count,其中count[i]就代表了岁数为i的人的个数。这样,当我们计算得到B的取值范围(a,b]之后,只要累加count数组在上下界范围(a,b]内的元素和就行了。显然,构造一个前缀和的方法是最高效的。