Largest Smallest Cyclic Shift
题目来源:
Atcoder Code Festival 2017 Qual B Problem F
题目大意:
有(X)个字符'a'
,(Y)个字符'b'
,(Z)个字符'c'
。用它们组成字符串,求最小表示的最大值。
思路:
贪心。首先将所有由单个字符构成的字符串插入到一个multiset<string>
中,每次选取最小串(s)和最大串(t)。此时最小表示一定是由(s)开头的,而将(t)接在(s)后面可以让最小表示尽可能大,因此可以将(s)和(t)从multiset
中删去,插入(s+t),最后仅剩一个串时将其输出即可。
源代码:
#include<set>
#include<cstdio>
#include<cctype>
#include<string>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
int main() {
std::multiset<std::string> set;
for(register int i=getint();i;i--) set.insert("a");
for(register int i=getint();i;i--) set.insert("b");
for(register int i=getint();i;i--) set.insert("c");
while(set.size()>1) {
std::string s=*set.begin(),t=*set.rbegin();
set.erase(set.lower_bound(s));
set.erase(set.lower_bound(t));
set.insert(s+t);
}
printf("%s
",(*set.begin()).c_str());
return 0;
}