摘要
Title: 1239. 乘积最大
Tag: 贪心
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1239. 乘积最大

• 题意

  给定 N 个整数 A1,A2,…AN。
  请你从中选出 K 个数，使其乘积最大。
  请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。
  注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)

• 思路

  
  在代码中实现时，就是如果$k$为奇数，那么就先选最大的数，让$k$变成偶数，如果最大的都是负数了，那么结果肯定是负数，也就是在以后比较时，得带着负号进行比较
  另外，负数和正数取时，都是成对取，哪个组合乘积大，选哪个

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-30 20:16:21
  FilePath: \ACM\Acwing\1239.py
  LastEditTime: 2022-03-30 20:16:22
  '''
  MOD = int(1e9 + 9)
  n, k = map(int, input().split())
  a = []
  for i in range(n):
      a.append(int(input()))
  
  a.sort()
  l, r = 0, n - 1
  res = 1
  sign = 1  #符号，1代表正，-1代表负
  if k & 1:
      res = a[r]
      r -= 1
      k -= 1
      if res < 0:
          sign = -1
  
  while k:
      x = a[l] * a[l + 1]
      y = a[r] * a[r - 1]
      if x * sign > y * sign:
          res = abs(res) * abs(x) % MOD
          l += 2
      else:
          res = abs(res) * abs(y) % MOD
          r -= 2
      k -= 2
  print(res * sign)