乘积末尾的0

区间删除

解题思路：

乘积末尾0的个数取决于2和5的因子的数量。因此我们要对所有的数进行统计2和5的因子个数。接下来使用滑动窗口算法： 构建一个滑动窗口，要求保证删除窗口内的元素后，保证剩余元素的乘积末尾0的个数>=k。因此只要窗口内的元素被删除不影响结果，右指针r依旧可以向右移动；否则，需要把左指针l向右移动,直至r到边界结束。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<int> a2(n,0);
    vector<int> a5(n,0);
    int cnt2=0,cnt5=0;
    for(int i=0;i<n;i++){
        while(arr[i]%2==0){
            a2[i]++;
            cnt2++;
            arr[i]=arr[i]/2;
        }
        while(arr[i]%5==0){
            a5[i]++;
            cnt5++;
            arr[i]=arr[i]/5;
        }
    }
    long long res=0;
    int l=0,r;
    for(int r=0;r<n;r++){
        cnt5-=a5[r];
        cnt2-=a2[r];
        while(min(cnt2,cnt5)<k&&l<=r){
            cnt2+=a2[l];
            cnt5+=a5[l];
            l++;
        }
        res+=(long long)(r-l+1);
    }
    cout<<res<<endl;
}

原文地址：https://blog.csdn.net/weixin_53287225/article/details/140390434

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！