Codeforces #374 721D. Maxim and Array

正文索引 [隐藏]

传送门:http://codeforces.com/problemset/problem/721/D

题目翻译

有一个长度为N的序列,每个操作可以给任意一个数+x/-x,至多进行k次操作,使序列乘积最小,输出方案。

题解

一个大讨论 + 线段树

  1. 如果序列里0的数量比操作数多,那么序列的乘积一定为0.直接输出,结束
  2. 如果序列里存在0,那么我们可以用其中的一个0把序列里的负数个数调成奇数个,其他0全部变成整数。转到4 。
  3. 我们找序列里正数最小/负数最大的那个数,然后看看能不能通过操作把他的符号倒置,如果不行,那么就用全部操作使这个数的绝对值最小即可,输出,结束。如果可以,那么把这个数的符号倒置,转到4。
  4. 因为存在奇数个负数,所以我们要使每个数绝对值乘积最大,秉承和一定积最大的原则,我们用每个数的绝对值建一颗线段树,然后每次给绝对值最小的数 + X ,暴力执行完剩余的操作次数。然后按照正负输出即可。

代码