time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a string s, consisting of lowercase English letters, and the integer m.
One should choose some symbols from the given string so that any contiguous subsegment of length m has at least one selected symbol. Note that here we choose positions of symbols, not the symbols themselves.
Then one uses the chosen symbols to form a new string. All symbols from the chosen position should be used, but we are allowed to rearrange them in any order.
Formally, we choose a subsequence of indices 1 ≤ i1 < i2 < … < it ≤ |s|. The selected sequence must meet the following condition: for every j such that 1 ≤ j ≤ |s| - m + 1, there must be at least one selected index that belongs to the segment [j, j + m - 1], i.e. there should exist a k from 1 to t, such that j ≤ ik ≤ j + m - 1.
Then we take any permutation p of the selected indices and form a new string sip1sip2… sipt.
Find the lexicographically smallest string, that can be obtained using this procedure.
Input
The first line of the input contains a single integer m (1 ≤ m ≤ 100 000).
The second line contains the string s consisting of lowercase English letters. It is guaranteed that this string is non-empty and its length doesn’t exceed 100 000. It is also guaranteed that the number m doesn’t exceed the length of the string s.
Output
Print the single line containing the lexicographically smallest string, that can be obtained using the procedure described above.
Examples
input
3
cbabc
output
a
input
2
abcab
output
aab
input
3
bcabcbaccba
output
aaabb
Note
In the first sample, one can choose the subsequence {3} and form a string “a”.
In the second sample, one can choose the subsequence {1, 2, 4} (symbols on this positions are ‘a’, ‘b’ and ‘a’) and rearrange the chosen symbols to form a string “aab”.
【题解】
假如m=3;
现在给了你一段序列
从1开始。
1-3里面必然要选一个
那么选什么呢?
肯定是选字典序最小的那个。
不然的话最后选出来的一定不是最优的
比如cab
你只能选a.
然后再从xiabiao[a]+1开始再选3个
cabbb
现在下标变成3
你需要从bbb中选择一个。当然还是选择最小的那个,这个时候你没得选了
只能选b.(记录字典序最大的变成了b)
但是为了节省时间。你需要尽量往后选。
比如cabbbzab
因为如果你选了第一个b
接下来就要从b,b,z这三个里面选一个最小的。
那还是b。。所以没有意义，直接从最后一个选开始选就好。
且
b z z z b
这样的数据如果不从最后一个b开始选。你会面临3个z的抉择。这下可就会错解了。
每次选定一个字母后，就尝试更新最大字典序的字母；
最后获得了最大字典序的字母key;
从’a’..’key’-1;按顺序添加到答案字符串的末尾；
对于key要单独处理。只有在m个m个地选的过程中不得不选key这个字符的时候才要选,即加到答案字符串末尾；
因为
假如key为b
aaabb小于aaabbb
即等于key的不能全选。那样可能会出错；
而之所以小于key的要全选
是因为
aabb小于abb
即从第一个不同的字母开始比较的。
和Pascal有点不一样。pascal是先比较长度。
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
const int MAXN = 2e5;
using namespace std;
vector <int> a[30];
string s;
bool vis[MAXN] = { 0 };
int m;
void input(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
input(m);
cin >> s;
int len = s.size();
for (int i = 0; i <= len - 1; i++)
a[s[i] - 'a'].push_back(i);
int i,mx = 0;
for (i = 0; i <= len - m; i++)
{
for (int j = 0; j <= 25; j++)//从小到大可以肯定找的是字典序最小的。
{
int k = upper_bound(a[j].begin(), a[j].end(), i + m - 1) - a[j].begin();//upper_bound则尽量靠后
k--;
int len = a[j].size();
if (k >= 0 && k <= len-1 && a[j][k] >= i && a[j][k] <= i + m - 1)
{
mx = max(mx, j);//找到之后就尝试更新最大字典序
i = a[j][k];//等于它的位置就好第一层for会+1
vis[a[j][k]] = true;//记录这个位置必须选
break;//记录这个是为了方便控制输出mx字符
}
}
}
string ans = "";
for (int i = 0; i < mx; i++)
{
len = a[i].size();
for (int j = 0; j <= len - 1; j++)
ans += (i + 'a');
}
len = a[mx].size();
for (int j = 0; j <= len - 1; j++)
if (vis[a[mx][j]])
ans += (mx + 'a');
cout << ans << endl;
return 0;
}