题解 | #游游的数组询问#

题目链接

游游的数组询问

题目描述

给定一个长度为 $n$ 的数组。每个数字的“权值”定义为其不同质因子的数量。

任务是需要从数组中删除一个长度恰好为 $k$ 的连续子数组，并使得剩余所有数字的权值之和最大。

求解这个最大的权值和。

解题思路

这个问题的目标是“最大化剩余部分的和”，这与“最小化删除部分的和”是等价的。因此，我们可以将问题转化为：在一个由权值组成的数组中，找到一个长度为 $k$ 的连续子数组，使其和最小。

解题步骤可以分为两步：

1. 计算每个数的权值

我们需要一个高效的方法来计算 $1$ 到 $10^5$ 范围内每个数的不同质因子数量。我们可以使用类似于 埃氏筛 的思想来预处理：

创建一个数组 prime_factors_count，大小为 $10^5 + 1$ ，并初始化为 $0$ 。
从 $i = 2$ 开始遍历到 $10^5$ 。
如果 prime_factors_count[i] 仍然为 $0$ ，说明 $i$ 是一个质数。
对于这个质数 $i$ ，遍历它在范围内的所有倍数 $j = i, 2i, 3i, \dots$ 。对于每个倍数 $j$ ，我们给 prime_factors_count[j] 加 1，因为它多了一个不同的质因子 $i$ 。

通过这个预处理，我们可以在 $\mathcal{O}(1)$ 的时间内查询到任何一个数的权值。之后，我们可以遍历原始输入数组，生成一个对应的 weights 数组。

2. 寻找最小和子数组

在得到了 weights 数组后，我们需要找到其中长度为 $k$ 的最小和连续子数组。这是一个经典的 滑动窗口 问题。

首先，计算 weights 数组的总和 total_weight。
计算初始窗口（即前 $k$ 个元素）的和 current_sum。将其设为当前的最小和 min_sum。
从第 $k$ 个元素开始，向右滑动窗口直到数组末尾。在每一步滑动中：
- 加上新进入窗口的元素。
- 减去离开窗口的元素。
- 更新 min_sum。
遍历结束后，我们就得到了长度为 $k$ 的子数组的最小和 min_sum。

最终的答案就是 total_weight - min_sum。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MAX_VAL = 100001;
int prime_factors_count[MAX_VAL];

void sieve() {
    for (int i = 2; i < MAX_VAL; ++i) {
        if (prime_factors_count[i] == 0) { // i 是质数
            for (int j = i; j < MAX_VAL; j += i) {
                prime_factors_count[j]++;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    sieve();

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    vector<int> weights(n);
    long long total_weight = 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        weights[i] = prime_factors_count[a[i]];
        total_weight += weights[i];
    }

    long long current_sum = 0;
    for (int i = 0; i < k; ++i) {
        current_sum += weights[i];
    }

    long long min_sum = current_sum;

    for (int i = k; i < n; ++i) {
        current_sum = current_sum - weights[i - k] + weights[i];
        min_sum = min(min_sum, current_sum);
    }

    cout << total_weight - min_sum << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MAX_VAL = 100001;
    private static int[] primeFactorsCount = new int[MAX_VAL];

    public static void sieve() {
        for (int i = 2; i < MAX_VAL; i++) {
            if (primeFactorsCount[i] == 0) { // i 是质数
                for (int j = i; j < MAX_VAL; j += i) {
                    primeFactorsCount[j]++;
                }
            }
        }
    }

    public static void main(String[] args) {
        sieve();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] a = new int[n];
        int[] weights = new int[n];
        long totalWeight = 0;

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            weights[i] = primeFactorsCount[a[i]];
            totalWeight += weights[i];
        }

        long currentSum = 0;
        for (int i = 0; i < k; i++) {
            currentSum += weights[i];
        }

        long minSum = currentSum;

        for (int i = k; i < n; i++) {
            currentSum = currentSum - weights[i - k] + weights[i];
            minSum = Math.min(minSum, currentSum);
        }

        System.out.println(totalWeight - minSum);
    }
}

MAX_VAL = 100001
prime_factors_count = [0] * MAX_VAL

def sieve():
    for i in range(2, MAX_VAL):
        if prime_factors_count[i] == 0:  # i 是质数
            for j in range(i, MAX_VAL, i):
                prime_factors_count[j] += 1

def main():
    sieve()
    
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    weights = [prime_factors_count[x] for x in a]
    total_weight = sum(weights)
    
    current_sum = sum(weights[:k])
    min_sum = current_sum
    
    for i in range(k, n):
        current_sum = current_sum - weights[i - k] + weights[i]
        min_sum = min(min_sum, current_sum)
        
    print(total_weight - min_sum)

if __name__ == "__main__":
    main()

算法及复杂度

算法：筛法预处理 + 滑动窗口
时间复杂度：
- 筛法预处理的时间复杂度约为 $\mathcal{O}(V_{\max} \log \log V_{\max})$ ，其中 $V_{\max}$ 是数组中元素的最大可能值 ( $10^5$ )。
- 将原数组转换为权值数组需要 $\mathcal{O}(n)$ 。
- 滑动窗口遍历一次权值数组，时间复杂度为 $\mathcal{O}(n)$ 。
- 因此，总时间复杂度由预处理主导，为 $\mathcal{O}(V_{\max} \log \log V_{\max} + n)$ 。
空间复杂度：需要一个数组来存储每个数的质因子数量，因此空间复杂度为 $\mathcal{O}(V_{\max})$ 。