计蒜客-星云系统--贪心--字典序

额额额额额额

我怎么这么菜呀!居然爆零了

https://nanti.jisuanke.com/t/39614

给定一个字符串s长度5e6,

求它的 最小字典序 定长k([1,|s|])子序列

妈呀...这是啥呀，我TM只求过最长上升子序列，这个不好搞呀，

1.刚开始想着弄个堆维护所有可选择的点,然而O(nlogn)爆炸了,,,,

隔壁老王玄学常数优化，过了,扎心

2.优化下，这玩意不是可以DP吗,dp[i][j]表示从第i个位置开始j字符第一次出现的位置

爆空间......貌似也没法优化，再次扎心了。。。。

3.官方题解,tql

思想：正难则反,贪心思想,利用性质-过度求解

分析:

性质1:如果不管字符串的结尾:那么最小k长子序列肯定是最小k+1长子序列的前缀：

因此，可以求出最小k+1子序列,k+2,或k+3......

性质2:留下k个字符就是删去n-k个(这不是废话嘛)

性质(方法)3:字符串子序列最优解中经常用的"替换方法",想一想,求LIS的过程中是不是也用到了替换?

那这个题目能不能用到替换呢？答案是:可以

解法:顺序遍历字符串,把字符放入答案中,然后尽量保持答案是非降序的(为什么呢?因为要保持字典序最小)

如果你能删去任意数量字符，你是不是可以维持非降序了?是的，但是必须删去n-k个，这里可以用到性质1了

你就当你最多可以删去n-k个，那么最后留下的字符串的长度是>=n-k的，>n-k怎么办?直接取前缀,完了

/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//简化敲击
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint> inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(20);
stack<char>S;
int k, n;
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	int T(1), cas(0);
#ifdef CPP_IO// CPP_IO
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (++cas, T--)
	{
		string s; cin >> s >> k;
		n = s.size();
		string ans;
		int cut(0);
		for (auto c : s)
		{
			while (cut<n-k&&ans.size() && ans.back() > c)
			{
				++cut; ans.pop_back();
			}
			ans += c;
		}
		ans = ans.substr(0, k);
		cout << ans << endl;
	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读，禁endl
1.数组越界，爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps)，取模操作，初始化数组，边缘数据,输出格式(cas)
2.通读代码，代码无逻辑错误
3.读题，找到题意理解失误或算法错误
4.放弃
*/