3.9美团笔试第4题【java】前缀和滑动窗口加二分优化

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        st.nextToken();
        int n= (int) st.nval;
        st.nextToken();
        int k= (int) st.nval;
        int[] a=new int[n+1];
        long[] a2=new long[n+1];
        long[] a5=new long[n+1];
        for (int i = 1; i < n + 1; i++) {
            st.nextToken();
            a[i]= (int) st.nval;
            a2[i]=a2[i-1]+cal(a[i],5);
            a5[i]=a5[i-1]+cal(a[i],2);
        }
        long tot2=a2[n],tot5=a5[n];
        long res=0L;
        for(int l=0;l<n;l++){ //删除区间必须得存在
            long zuo2 =tot2-k+a2[l];
            long zuo5 =tot5-k+a5[l];
            int findzuo2=findrm(zuo2,a2);
            int findzuo5=findrm(zuo5,a5);
            res+=Math.max(Math.min(findzuo2,findzuo5)-l,0);
        }
        System.out.println(res);
    }

    private static long cal(int shu, int yinzi) {
        long cnt=0;
        while(shu!=0&&shu%yinzi==0){
            cnt++;
            shu/=yinzi;
        }
        return cnt;
    }
    private static int findrm(long key, long[] arr) {
        int l=0,r=arr.length-1;
        while(l<=r){
            int mid=l+r>>>1;
            if(arr[mid]<=key)l=mid+1;
            else r=mid-1;
        }
        return r;
    }
}