M04137:最小新整数

monotonous-stack, http://cs101.openjudge.cn/practice/04137/

思路：

法一（考场 ver.）：注意到 $n$ 最多只有 $9$ 位，因此可以直接枚举出所有可能的删除方案，再取最小值即可。时间复杂度视实现可能为 $O (t 2^{m} m)$ 或 $O (t C_{m}^{k} (m - k))$ ，其中 $m = ⌊ \log_{10} n ⌋ + 1$ 。
法二：考虑 dp，设 $d p_{i, j}$ 表示在前 $i$ 位中删去 $j$ 位所能得到的最小数，答案即为 $d p_{m, k}$ 。时间复杂度为 $O (t m k)$ 。
法三：考虑贪心，令 $k^{'} = m - k$ ，则我们需要给新数依次确定尽可能小的第 $i$ 位，其中 $i = 1, \dots, k$ 。
设新数的第 $t$ 位为原数的第 $p_{t}$ 位，原数从高到低的第 $t$ 位为 $d_{t}$ ，则对于 $p_{i}$ ，我们有如下限制：
(1) $p_{i - 1} < p_{i} \leq n - (k^{'} - i) = i + k$ ，左边确保了新数的前 $i$ 位可以通过删除原数得到，右边确保了第 $i + 1 \sim k^{'}$ 位还有的选。
(2) $d_{p_{i}}$ 尽可能小。那要是有多个，我们应该怎么办呢？
(3) 在满足 (2) 的前提下， $p_{i}$ 尽可能小，这样的话可以给后面留下更大的选择余地。
类似滑动窗口地单调队列即可。时间复杂度为 $O (t m)$ 。
~~那么问题来了，为什么 $n$ 不开到 $10^{10^{5}}$ 卡掉上面两种做法？~~

代码（法三）：

cpp

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int digit[10];
deque<int> q;

int main(){
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++){
		int n, k, k_, len = 0;
		cin >> n >> k;
		while (n > 0){
			digit[++len] = n % 10;
			n /= 10;
		}
		reverse(digit + 1, digit + len + 1);
		k_ = len - k;
		q.clear();
		for (int j = 1; j <= k; j++){
			while (!q.empty() && digit[q.back()] > digit[j]) q.pop_back();
			q.push_back(j);
		}
		for (int j = 1; j <= k_; j++){
			int add = j + k, cur;
			while (!q.empty() && digit[q.back()] > digit[add]) q.pop_back();
			q.push_back(add);
			cur = q.front();
			q.pop_front();
			cout << digit[cur];
		}
		cout << endl; 
	}
	return 0;
}

M04137:最小新整数 ​

M04137:最小新整数