贪心，CF721 D. Maxim and Array

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 721D - Codeforces

二、解题报告

1、思路分析

如果我们当前乘积为正，那么我们首先要将乘积调整到非正（注意不一定是负）再继续求解，这一步很好想，找到绝对值最小的元素将其调整变号即可（注意变号有可能是变为0，为什么调整到0和后面的策略有关）

我们最终的结果有两种情况，正值/非正值

1. 结果是正数的情况

   1. 初值为正，使绝对值最小数变号所需次数不够，那我们只能使得最后结果是正的。我们发现将绝对值最小的数变号即调整到0最优。否则，如果我们将a、b(a < b)两个元素分别操作ka、kb次，那么(a - ka * x)(b - kb * x) = ab - bka * x - akb * x + ka * kb * x^2 >= ab - b ka * x - bkb * x = b * (a - (ka + kb) * x)，故得证。所以当无法调整变号时，我们调整绝对值最小的数是最优的

2. 结果是负数的情况

   1. 调整完后，我们整体乘积应该是小于等于0的
   2. 我们先考虑小于0了已经，那么剩下元素该如何调整呢？——每次操作应当选择绝对值最小的进行操作，因为一次操作后的乘积和操作前的乘积比值为|a| + x / |a|，显然|a|越小越好
   3. 现在来考虑0，原数组中是有一部分0的，我们应该对0/1 个0进行-x操作，剩下的0进行+x操作，如果不懂可以看代码理解，这个不好叙述

2、复杂度

时间复杂度： O(nlogn)空间复杂度：O(n)

3、代码详解

​

import heapq
import sys

n, k, x = map(int, input().split())
nums = list(map(int, input().split()))

neg = sum(1 for a in nums if a < 0) & 1

if not neg:
    mi = 0
    for i in range(n):
        if abs(nums[i]) < abs(nums[mi]):
            mi = i

    dec = (abs(nums[mi]) - 1) // x + 1

    if k < dec:
        nums[mi] += k * x if nums[mi] < 0 else k * -x
        print(' '.join(map(str, nums)))
        exit()
    if nums[mi] < 0:
        neg = True
    k -= dec
    nums[mi] += dec * x if nums[mi] < 0 else dec * -x

pq = [abs(nums[i]) * n + i for i in range(n)]
heapq.heapify(pq)
for _ in range(k):
    i = heapq.heappop(pq) % n
    if nums[i] == 0 and not neg:
        nums[i] -= x
        neg = True
    else:
        nums[i] += x if nums[i] >= 0 else -x
    heapq.heappush(pq, abs(nums[i]) * n + i)
print(' '.join(map(str, nums)))