CF1009B Minimum Ternary String
string minimum
2023-09-11 14:20:14 时间
CF1009B Minimum Ternary String
题目描述
给定一个由 '0', '1', '2' 组成的字符串 SSS 。可以交换相邻'0', '1'或'1', '2'的位置(例如:'12' - '21' ; '01' - '10')请输出原字符串经过任意转换后字典序最小的字符串。原字符串长度不超过 10510^5105 。
输入格式
字符串 SSS
题解:
一看就是推性质的题。要说是贪心其实也可以。
0要靠前,1尽可能在2前面,2靠后。
然后看怎么移动。
发现如果2后面有0,这个0打死也动不到这个2的前面,因为到后面就截止了。
发现1非常自由,可以到序列的任何一个位置。
那么贪心思路就是:保留0、2,把所有的1放到第一个2的前面。
有这个思路就好办了。
剩下的是一些细节。
代码:
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e5+5;
char a[maxn];
bool flag;
int pos,cnt;
int main()
{
scanf("%s",a+1);
int len=strlen(a+1);
for(int i=1;a[i];i++)
{
if(a[i]=='1')
cnt++;
if(a[i]=='2'&&!flag)
{
flag=1;
pos=i;
}
}
if(cnt==len)
{
for(int i=1;a[i];i++)
printf("%c",a[i]);
return 0;
}
for(int i=1;a[i];i++)
{
if(a[i]=='1')
continue;
else if(i==pos)
for(int j=1;j<=cnt;j++)
printf("1");
printf("%c",a[i]);
}
if(!pos)
for(int j=1;j<=cnt;j++)
printf("1");
return 0;
}
相关文章
- String.prototype.charCodeAt()和String.fromCharCode()
- BZOJ4963 : String
- 2015 Multi-University Training Contest 6 hdu 5362 Just A String
- JAVA字符串格式化-String.format()的使用 及 Android 中 string.xml 中 字符串格式转化
- emoji错误:ER_TRUNCATED_WRONG_VALUE_FOR_FIELD: Incorrect string value:
- TypeError: Property value expected type of string but got null
- 前后台JSON传值得一个问题和异常处理net.sf.json.JSONException: Unquotted string '"name"'
- js中找string中重复项最多的字符个数
- ZOJ 3587 Marlon's String 扩展KMP
- C++ 基础入门 之 sizeof/int/short/long/float/double/char/转义字符/char[]/string/ bool/数据的输入输出 cin/cout
- leetcode——Reverse Words in a String 旋转字符串中单词顺序(AC)
- [LeetCode] 1312. Minimum Insertion Steps to Make a String Palindrome 让字符串成为回文串的最少插入次数
- [LeetCode] 839. Similar String Groups 相似字符串组
- [LeetCode] First Unique Character in a String 字符串第一个不同字符
- string to char* and char* to string 玩转 String 和 Char*
- Converting a MatchCollection to string array