游游的数组询问

[编程题]游游的数组询问

热度指数：564 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游有一个长度为 $n$ 的数组，每个数的权值为它的质因子个数。现在游游想要删除一段长度刚好为 $k$ 的子数组，删除后需要使剩下的数的权值和最大。问这个权值和是多少？

输入描述:

第一行两个整数 。
接下来一行  个正整数 。

输出描述:

输出一个整数，表示答案。

示例1

输入

5 2
6 2 4 1 3

输出

说明

1没有质因子，权值为0。
2的质因子是2，权值为1。
3的质因子是3，权值为1。
4的质因子是2，权值为1。
6的质因子是2和3，权值为2。
删除子数组 [4,1]，剩下的数是6,2,3，权值总和为4。

算法知识视频讲解

查看答案及解析

C/C++

已注销

因为求的是子数组，并给定删除子数组长度为k，那么可以对整个数组求出每个数字质因数个数。

因为子数组代表连续的，可以枚举连续子数组的左端点，设其为i，可以求出右端点即i + k - 1，答案就是前i - 1个数字质因数个数之和加上从i + k到最后一个数字的质因数个数之和，这两部分可以用前缀和和后缀和来做，具体细节见代码：

#include <bits/stdc++.h>

using namespace std;

signed main() {
    int n, k;
    cin >> n >> k;

    vector<int> pre(n + 10), suf(n + 10), cnt(n + 10);
    // cnt[i]表示第i个数字不同质因数的个数
    // pre[i]表示从第1个数字的不同质因数个数加到第i个数字的不同质因数个数
    // suf[i]表示从第i个数字的不同质因数个数加到第n个数字的不同质因数个数

    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        
        int count = 0, b = a; // count代表数字a有多少个不同的质因数
        for (int j = 2; j <= a / j; j++) { // 进行质因数分解
            if (b % j == 0) {
                count ++ ;
                while (b % j == 0) b /= j;
            }
        }

        if (b > 1) count ++ ;

        cnt[i] = count;
        pre[i] = pre[i - 1] + cnt[i]; // 前缀和
    }

    for (int i = n; i; i--) suf[i] = suf[i + 1] + cnt[i]; // 后缀和

    int ma = 0;

    for (int i = 1; i + k - 1 <= n; i++) {
        ma = max(ma, pre[i - 1] + suf[i + k]); // 求答案
    }

    cout << ma << '\n';

    return 0;
}

发表于 2025-07-17 14:50:35 回复(0)

geniecyy

import sys,heapq

n,k=list(map(int,input().strip().split()))
a=list(map(int,input().strip().split()))


def cnt_prime(u):
    ans=0
    i=2
    
    while i<=u:
        
        if u%i==0:
            while u%i==0:
                u=u//i
            ans+=1
        i+=1
    return ans
prisum=[0]*(n+1)
for i in range(n):
  
    prisum[i+1]=prisum[i]+cnt_prime(a[i])



    
m=float('inf')
for i in range(1,n+1):
    j=i-k
    if j>=0:
        m=min(m,prisum[i]-prisum[j])
    
print(prisum[n]-m)
   为啥超时了

发表于 2025-09-09 12:28:43 回复(1)