5959. 使数组 K 递增的最少操作次数

5959. 使数组 K 递增的最少操作次数

分组LIS

class Solution {
public:
    int calc(vector<int>arr){
        int n=arr.size();
        vector<int>stk(n+10);
        int top=0;
        for(int i=0;i<n;i++){
            int l=0, r=top;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(stk[mid]<=arr[i])l=mid;
                else r=mid-1;
            }
            stk[r+1]=arr[i];
            top=max(top,r+1);
        }
        return top;
    }
    int kIncreasing(vector<int>& arr, int k) {
        int res=0, n=arr.size();
        for(int i=0;i<k;i++){
            vector<int>nums;
            int j=i;
            while(j<n){
                nums.push_back(arr[j]);
                j+=k;
            }
            res+=nums.size()-calc(nums);
        }
        return res;
    }
};