1021 ModricWang的序列问题II
思路
此题与上一题区别不是很大，只是增加了一个长度限制，当场通过的人数就少了很多。
大体解题过程与上一题相同。区别在于对\(f[]\) 的操作。没有长度限制的时候，\(f[]\) 的更新策略是立即更新。假设间隔为\(T\)，现在由于需要考虑间隔，那么在处理第\(i\) 个元素的时候，就需要看到 前\(i -T\) 个元素生成的\(f[]\) ，而不能受到第\(i-T+1\) 到 \(i-1\) 个元素的干扰。因此，考虑如下操作：每次准备更新\(f[]\) 时，先不要更新，记录下操作的内容，过\(T\) 步再进行操作，这样就可以让\(f[]\) 不再显示当前元素之前\(T\) 步的修改内容，每次更新都不受前\(T\) 步的影响，因此生成的序列中相邻元素的间隔都是不小于\(T\) 的。
代码
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 500010;
int nums[MAXN], pool[MAXN];
queue<pair<int, int>> buffer;
//用二分查找的方法找到一个位置，使得num>pool[i-1] 并且num<pool[i],并用num代替b[i]
int Search(int num, int low, int high) {
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (num > pool[mid]) low = mid + 1;
else high = mid - 1;
}
return low;
}
int DP(int n, int k) {
while (!buffer.empty())buffer.pop();
int i, len, pos;
pool[1] = INT_MAX;
len = 1;
for (i = 1; i <= n; i++) {
if (nums[i] > pool[len]) { //如果a[i]比b[]数组中最大还大直接插入到后面即可
buffer.emplace(nums[i], len + 1);
} else { //用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置
pos = Search(nums[i], 1, len);
buffer.emplace(nums[i], pos);
}
while (buffer.size() >= k) {
if (buffer.front().second > len) {
len = buffer.front().second;
pool[buffer.front().second] = buffer.front().first;
} else if (buffer.front().first < pool[buffer.front().second]) {
pool[buffer.front().second] = buffer.front().first;
}
buffer.pop();
}
}
while (!buffer.empty()) {
if (buffer.front().second > len) {
len = buffer.front().second;
pool[buffer.front().second] = buffer.front().first;
} else if (buffer.front().first < pool[buffer.front().second]) {
pool[buffer.front().second] = buffer.front().first;
}
buffer.pop();
}
return len;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> nums[i];
cout << DP(n, k) << "\n";
}