c++ - 数字的最大 K 积

Question

任务 - 数字的最大 K 积
时间限制:1
内存限制:64 M
给定一个整数序列 N(1 ≤ N ≤ 10 月，| A i | ≤ 2.10 9)和数量 K(1 ≤ K ≤ N)。找出乘积最大的 K 个序号。

输入数据:
第一行包含两个整数N和K。
第二行列出了序列A的N个元素。

输出数据:
导出最大乘积。所以答案可能很大，输出它模 10^9+7。

例子
输入数据的结果
3 2
-2 -3 3

答案 - 6

下面是我的尝试。这是一个错误，这就是我不知道的。你能帮我找出错误的决定吗？

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> v1;
const int mod = 1000000007;
int n, k, pos1 = 0, pos2 = 0, negative = 0;
long long res = 1;
void QuickSort(v1 &a, int l, int r) {
  int i = l, j = r, pivot = abs(a[l + ((r - l) >> 1)]);
  do {
        while (abs(a[i]) < pivot) i++;
        while (abs(a[j]) > pivot) j--;
        if (i <= j) {
            int temp = a[i];
            a[i++] = a[j];
            a[j--] = temp;
        }
    } while (i < j);
    if (l < j) QuickSort(a, l, j);
    if (i < r) QuickSort(a, i, r);
}

long long product(v1 &a, v1 &b, int q, int j, char flag) {
    long long res = 1; int temppos;
    if (flag == 0 && j) {
        temppos = b[pos1];
        b[pos1] = j;
    }
    if (flag == 1 && q) {
        temppos = b[pos2];
        b[pos2] = q;
    }
    if (!pos2 && (k & 1)) {
        for (int i = 1; i <= k; i++)
            res = (long long)((res % mod)*1ll*(a[i] % mod)) % mod;
    } else {
        for (int i = 1; b[i] != 0; i++)
            res = (long long)((res % mod)*1ll*(a[b[i]] % mod)) % mod;
    }
    if (flag == 0 && j) b[pos1] = temppos;
    if (flag == 1 && q) b[pos2] = temppos;
    return res;
}

int main()
{
      v1 a(100002, 0);
        v1 b(100002, 0);  //index multiplied to the elements
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i];
        QuickSort(a, 1, n);
        for (int i = n, j = 1; i > n - k; i--) {
                b[j] = i;
                if (a[i] < 0) {                     
                    pos1 = j;    //index last positive number 
                    negative++;  //increase the counter negative numbers
                }
                  else pos2 = j;  //index last positive number                
                j++;
        }
        int j = n - k, q = j;
        if (negative & 1) { //If an odd number of negative numbers
            while (j > 0 && a[j] < 0) j--;
            while (q > 0 && a[q] > 0) q--;
            res = max(product(a, b, q, j, 0), product(a, b, q, j, 1));
        } else res = product(a, b, q, j, 3);
        cout << res << endl;
    cin >> res;
    return 0;
}

Answer 1

首先:您的代码非常密集和困惑，所以我将在这里给出我自己的方法和思考过程。

所以我的第一个想法是关于所有输入整数都是正数的情况。将我们的源数组(包含 N 个整数的数组)称为 A。

• 初始化一个包含 A 的前 K 个元素的数组 B。
• 对于满足 K <= i <= n 的每个 i，检查 A[i] 与 B 中的每个元素。如果 A[i] 大于某个 B[j]，则用 A[i] 替换 B[j] ].
• 完成后，将 B 的内容乘以 10^9 + 7 的模。

这需要 O(KN) 的时间，所以如果 K 的增长速度比 O(lg(N)) 慢，它就会比快速排序更快，也更简单。您可以通过使用树或堆来存储 B 来改进 O(N lg(K)) 的时间限制，但这超出了职责范围。

我的解决方案的问题在于，该问题将负数作为输入。现在，如果“答案 - 6”的意思是“答案是 -6 = -2 * 3”，并且你要求的是最大幅度的乘积，你需要做的就是取上面每个输入数字的幅度程序。但是您的代码表明您的意思是“答案是 6 = -2 * -3”，在这种情况下事情会稍微复杂一些。

看，如果最大乘积包含两个(或偶数个)负整数(如 (6 = -2 * -3) 的示例)，我的方法将不起作用，因为排序例程会丢弃负数到列表的底部。

相反，我们需要做的是保留三个数组:A，我们的输入数组； B，目前遇到的K个最大正数数组；和 C，一组 最小的负数(为避免混淆:在列表 -2 -3 -4 中，两个最小的负数是 -3 和 -4)到目前为止遇到的数。

当我们使用与上述类似的例程提取 B 和 C 后，我们需要将它们组合起来。我能想到的最好的方法是先对 B 和 C 进行排序，然后

• 计算 B 中所有数字对 10^7+9 的乘积。将其记录为 MAX。
• 用 C 中的两个最小(最负)数替换 B 中的两个最小数。
• 再次计算B中所有数的乘积，如果大于当前的MAX，则更新MAX。
• 将 B 中的两个最小正数 数替换为 C 中的下一个两个最小数。
• 重复，直到你完全通过 C。

这需要 O(K^2) 左右的时间，您也许可以通过更聪明的方法再次加快速度(比如当您插入的负数对的乘积的大小小于乘积时停止替换你要替换的正数对)，但这是我能想到的最清晰的一个。