ABC173 E. Multiplication 4
問題
N個の整数A_iが与えられる。
この中からK個の要素を選び、それらの積が最大になるものを答えよ。
ただし、積は10^9+7で割ったあまりで答えよ。
制約
- 1 <= K <= N <= 2*10^5
- | A_i | <= 10^9
解法
まず、負、0、正に分類し、パターンに分けて考える。
「負」の数＋「正」の数がKに足りない場合、必ず0を使わないといけなくなるため、答えは0になる。
また、K=1の場合は、「正」「0」「負」の順に一番大きい数字があるものを1つ返せば良い。
したがって、上記を除いた、
- 「負」の数＋「正」の数がK以上ある
- K >= 2
の場合を考えれば良い。
まず、Kが奇数の場合は、「正」の数を必ず1つ以上含めないといけない。
したがって、「正」で最大のものを先に入れておくことでKを偶数の場合と同様に考えることができる。
次に、Kが偶数の場合、「負」を2個いれるか、「正」を2個いれるかを考えれば良い。
「正」が1個だけ入れる場合は、必ず後で「正」のものを1個入れないとパリティが合わないので、2個入れると考えて良い。
したがって、「負」の昇順で連続する2個と「正」の降順で連続する2個を作り、その掛け算の大きさが大きい順にK/2個になるよう選べば良い。
上記でK個選べない場合は、「0」を入れて答えを0にするが、「0」がなければ「負」と「正」の整数の絶対値が小さいものからK個かけ合わせた負の値を返せばよい。
