1. 题意
给定一个数组 arr ，给定一个数 k ，对数组任意位置任意元素进行修改，使得其满足：
arr[i−k]<=arr[i]
求其最少修改次数
样例：arr = [5,4,3,2,1], k = 1
输出：4
解释：对于 k = 1 ，数组最终必须变成非递减的。显然我们无法使用少于 4 次操作将数组变成 K 递增的。
2. 算法
贪心 + 二分
3. 思路
由于要保证相隔 k 位的每一个序列都要不递减，那么我们可以拆分成 k 个互不干扰的子序列
贪心： 会拆出 k 个序列，每个序列做一遍，能保证所有元素都满足条件。
二分： 对每个序列求其最长不递减子序列的元素个数，而我们修改的最少步数即为该序列长度减去求得元素个数。
时间复杂度：O(nlogn)
可以对比最长上升子序列细节的不同:
最长上升子序列：lower_bound
最长不递减子序列：upper_bound
代码
class Solution { public: int kIncreasing(vector<int>& arr, int k) { int n = arr.size(); int res = 0; for (int i = 0; i < k; i++) { vector<int> a; for (int j = i; j < n; j += k) a.push_back(arr[j]); int m = a.size(); vector<int> f(m, 0x3f3f3f3f); for (int j = 0; j < m; j++) { int d = upper_bound(f.begin(), f.end(), a[j]) - f.begin(); f[d] = a[j]; } res += m - (lower_bound(f.begin(), f.end(), 0x3f3f3f3f) - f.begin()); } return res; } };
