请你从中选出 K 个数使其乘积最大。
请你求出最大的乘积由于乘积可能超出整型范围,你只需输出乘积除以 的余数
注意,如果 X<0 我們定义 X 除以 的余数是负(?X)除以 的余数,即:0?((0?x)%)
第一行包含两个整数 N 和 K
以下 N 行每行一个整数 Ai。
输出一个整数表示答案。
首先肯定:负数和正数都是尽可能成对选择的。
特殊凊况:①、N=K,那么结果ans即所有数Ai?的乘积对1e9+9取模。
Ⅰ、若K是偶数,那麼结果恒正选绝对值最大的2m个负数和K?2m个正数相乘,m<=2K?。
Ⅱ、若K是奇数只要存在正数,那么结果恒正先选一个最大正数,再选绝对值最大的2m个负数和K?1?2m个正数相乘m<=2K?1?。否则(这里是值得留意的地方)将绝对值最小的K个负数相乘。
综上:①、K是偶数从正、负数中两两选择乘积更大的数。
对整个数列先排序,然后双指针一前一后选择乘积更大的两个数
注意:′?′ 和 ′%′运算的优先级相同故运算时从左向右结合的,在计算ans过程中顺序不能出错
ST表类似树状数组、线段树
适用於解决区间最值得查询得算法,预处理O(nlogn)查询上ST表为O(1),而线段树为O(logn)但是ST表只能除了离线的,不能修改
题意:n个数,m次查询 每次查询給一个区间,让你求该区间里面的最大值
题意:给定 n 个点对 ( pi , di ) ,求出所有的点对使得对于当前点对来说,不存在其它点对的 p, d 比这个点对嘚都小按照 p 优先,d 次先从小到大输出点对
题解:将其按照p为第一优先级,d为第二优先级从小到大排序,用ST表存d