【每日一题】打卡 55

原题链接：Problem - N - Codeforces

题意：给你一个正整数x。您可以对数字应用以下操作：

删除任何数字的一个出现，以使生成的数字不包含任何前导零，并且仍然是正整数。例如，10142可以转换为1142、1042、1012或1014（注意0142不是有效结果）；10可以转换为1（但不能转换为0，因为它不是正的）。您的任务是找到从x中获得的最小正整数，如果您可以将上述操作精确应用k次。

思路：根据题意，我们需要选出n-k个数字，使它成为x中删除k数字的最小正整数。所以我们一位一位来看，除了第一位数字，每位的数字遍历0~9，看看是否能找到能选的最小的数字，若能找到则输出它。而判断该数字是否能选的条件：

1.该数字的下标大于上一位选择的数字。

2.剩下的数字若全部选完要大于等于n-k，要不然就会出现选择数字过少的情况。

最后我们可以采用map+优先队列的形式来存储每个数字的下标，当然，优先队列必须是大顶堆，因为在相同的数字里，肯定是先选下标较小的数字。

void solve() {
	map<int, priority_queue<int, vector<int>, greater<int> > > mp;
	string s;
	int k, n, lst = -1, sum;
	cin >> s >> k;
	n = s.size();
	sum = n - k;
	FOR(0, n - 1) mp[s[i] - '0'].push(i);
	FOR(0, n - 1 - k) {
		FORj(i == 0 ? 1 : 0, 9) {
			while (!mp[j].empty() && mp[j].top() < lst) mp[j].pop();
			if (!mp[j].empty() && n - mp[j].top() >= sum) {
				sum--;
				cout << j;
				lst = mp[j].top();
				mp[j].pop();
				break;
			}
		}
	}
	cout << endl;
}