求将数组转换为满足A[i]≤A[i+K]的好数组的最少操作次数

给定包含N个整数的数组A和整数K，若数组对所有i=1,2,…,n-K满足A[i]≤A[i+K]，则称为好数组。每次操作可将任意元素改为任意整数，数组采用1-based索引，请确定将数组变为好数组所需的最少操作次数。

你的核心思路是正确的：将原数组按间隔K拆分为K个独立子序列，每个子序列单独调整为非递减序列即可满足好数组的要求。每个子序列的最少修改次数 = 子序列长度 - 子序列的最长非递减子序列（LNDS）长度，累加所有子序列的修改次数就是最终答案。

原代码存在两处错误导致结果部分正确：

• 语法错误：lis函数中b[idx] = a[I]; 使用了大写的I，C++大小写敏感，该变量未定义，会直接编译失败，替换为小写的i即可。
• 逻辑错误：求最长非递减子序列时，你使用lower_bound查找替换位置，这是求严格递增子序列的实现，会漏算相等元素的合法场景，导致得到的LNDS长度偏短，最终计算的操作次数偏大。正确的实现应该使用upper_bound查找第一个大于当前元素的位置进行替换。

修正后的完整代码 #

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

int lis(vector<int>& a){
    if(a.size() == 0) return 0;
    vector<int> b;
    b.push_back(a[0]);
    for(int i = 1; i < a.size(); i++){
        if(b.back() <= a[i]) {
            b.push_back(a[i]);
        } else {
            int idx = upper_bound(b.begin(), b.end(), a[i]) - b.begin();
            b[idx] = a[i];
        }
    }
    return b.size();
}

int minOperations(int n, vector<int> a, int k){
    int cost = 0;
    for(int i = 0; i < k; i++){
        vector<int> b;
        for(int j = i; j < n; j+=k) {
            b.push_back(a[j]);
        }
        cost += b.size() - lis(b);
    }
    return cost;
}

内容的提问来源于stack exchange，提问作者SHARMIN AHMED