这道题不错。
题目意思:
数组item[i][0] item[i][0]表示每个物品的价格和美丽值。querys表示一系列的询问。
对于每个询问x,求价格 <= x的最大美丽值。
思路
这道题有两种解法,一种是离线算法,一种是在线算法。
离线的话就是:对querys进行排序。就会出现一种特征,因为现在询问的价格是有序的,所有,当处理下一个询问时,相当于优化了一部分。
例如:
知道了询问价格3, 即系小于等于3的最大漂亮值是5
那么 ,下一个询问7, 他的漂亮值一定大于5,
只需要再加个3-7之间求最大值r, mx = max(r, 5)
在线算法:
需要一个技巧,前缀最大值。
然后使用二分。