0313携程笔试开发方向第三题思路代码

思路：考虑埃氏筛法预处理出1e4每个数的质因子个数，之后滑动一个大小为k的窗口。只需要找到权值最小的窗口将其删掉，那么数组总权值减掉这个最小值就是答案。

#include <bits/stdc++.h>
using namespace std;

vector<int> shai() {
    int n = 1e4;
    vector<int> cnt(n + 1, 0);
    vector<bool> p(n + 1, false);
    for (int i = 2; i <= n; i++) {
        if (!p[i]) {
            for (int j = i; j <= n; j += i) {
                cnt[j]++;
                p[j] = true;
            }
        }
    }
    return cnt;
}

int main() {
    vector<int> cnt = shai();
    int n, k;
    cin >> n >> k;
    if (k == n) {
        cout << 0 << endl;
        return 0;
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> b(n);
    long long tot = 0;
    for (int i = 0; i < n; i++) {
        b[i] = cnt[a[i]];
        tot += b[i];
    }
    long long now = 0;
    for (int i = 0; i < k; i++) now += b[i];
    long long res = now;
    for (int i = k; i < n; i++) {
        now += b[i] - b[i - k];
        res = min(res, now);
    }
    cout << tot - res << endl;
    return 0;
}