Minimizing the String - CodeForces1076A

思维题真的是好玩啊哈哈哈,本来这个题感觉挺头疼的,但是突然来到的灵感就直接把这题A掉了233333


You are given a string s consisting of n lowercase Latin letters.

You have to remove at most one (i.e. zero or one) character of this string in such a way that the string you obtain will be lexicographically smallest among all strings that can be obtained using this operation.

String s=s1s2…sn is lexicographically smaller than string t=t1t2…tm if n<m and s1=t1,s2=t2,…,sn=tn or there exists a number p such that p≤min(n,m) and s1=t1,s2=t2,…,sp−1=tp−1 and sptp.

For example, “aaa” is smaller than “aaaa”, “abb” is smaller than “abc”, “pqr” is smaller than “z”.

Input

The first line of the input contains one integer n (2≤n≤2⋅105) — the length of s.

The second line of the input contains exactly n lowercase Latin letters — the string s.

Output

Print one string — the smallest possible lexicographically string that can be obtained by removing at most one character from the string s.

Examples

Input
3
aaa
Output
aa

Input
5
abcda
Output
abca

Note

In the first example you can remove any character of s to obtain the string “aa”.

In the second example “abca” < “abcd” < “abcda” < “abda” < “acda” < “bcda”.

大意:给你一个长度为n的仅由小写字母组成的字符串s,要求你最多删去一个字符,使新串字典序尽可能小,输出最小的字典序的串。

当时读完题,感觉这题暴力找每个可能的串然后比较字典序大小就好了啊。。。但是一看n有1e5级别啊,感觉有点悬,出于侥幸心理就试了一下,结果当然是T掉。中间有考虑过把Sometimes TLE Library换成char*继续暴力,但是理智阻止了我这么做 (:з」∠) 。。。

后来我想,可不可以找出出现的第一个最大的字符然后删掉?我当时脑抽,没办法证明它是正确还是错误,于是就交了一份上去,果然收获了一个WA。

于是我开始冷静分析。试想,如果这个序列是上升的,比如abcde这种,那么很显然是要把最大的删掉,那么要删掉e,如果这个序列是下降的,比如edcba,那么还是要把最大的删掉,还是要删掉e,这里很容易就掉进去一个思维误区,就是删掉最大的就可以,实际上是存在反例的。

如果这个序列有上升也有下降,比如说abcdedcba,还是要删掉最大的e,如果说这个序列有好几段上升和下降,比如说abcbabcdecba,还能删掉e吗?

对于abcbabcdecba,如果简单的删掉e,那么会变成abcbabcdcba,看起来好像没啥问题,但是。。。这是字典序最小的吗?

其实这个题最大的坑点就是逮着这个最大字母不放,那样这个题就根本A不了。

根据分析发现,如果要删除某个字母,显然只能在一个递减的子序列中删除。为什么?如果你在一个递增的子序列中删除一个数,下一个补上来的字母肯定比原来这一位上的高,比如abc删掉b变成ac,这时候它的字典序就肯定变大了,就不满足题意了。

所以,我们应该去关心那些递减的子串。

根据字典序的排序规则,越靠左的字符“权重”越高。比如说abz和aca,显然是abz要比aca小,尽管z比a大,但是我们要先考虑之前的b和c,所以才能说abz比aca小。所以要想让字典序尽量的小,就得优先考虑前边的串才行。

所以回到刚才的abcbabcdecba,我们试试关心前面的cba。发现如果改为删掉c,序列是abbabcdecba。和之前删掉e的答案放在一块对比一下:

abbabcdecba
abcbabcdcba

这里就发现问题了。在第三位,上边的串字典序是要更小的。所以不难印证上边的结论:只需要找到第一个下降的地方就可以。如果在某个位置,记为i,也就是说s[i] < s[i - 1],这时候就会发现,是i-1第一次破坏掉了整个序列的递增,所以把它删掉就可以保证字典序最小,因为之前没有比它“权值”更大的字母影响。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#define maxn 200005
using namespace std;
string s;
int n;
char bigc;
int bigpos;
bool flag = false;
int main() {
cin >> n;
cin >> s;
for (int i = 1; i < n; i++) {
if (s[i] < s[i - 1]) {
bigpos = i - 1;
bigpos = i - 1;
flag = true;
break;
}
}
if (!flag) {
for (int i = 0; i < n - 1; i++)
cout << s[i];
}
else {
for (int i = 0; i < n; i++) {
if (i != bigpos)
cout << s[i];
}
}
// system("pause");
return 0;
}

-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:Minimizing the String - CodeForces1076A

文章作者:Shawn Zhou

发布时间:2018年12月07日 - 20:12

最后更新:2019年01月18日 - 19:01

原始链接:http://shawnzhou.xyz/2018/12/07/18-12-07-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。