题目要求：
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个只包含小写字母'a'-'z'的字符串 S ，你需要将 S 中的字符重新排序，使得任意两个相同的字符不连在一起。
如果有多个重排后字符串满足条件，输出字典序最小的一个。
如果不存在满足条件的字符串，输出INVALID。
输入
字符串S。(1 ≤ |S| ≤ 100000)
输出
输出字典序最小的答案或者INVALID。
样例输入
aaabc
样例输出
abaca
《分隔相同字符》题目分析
首先我们需要分析INVALID的充分必要条件。容易看出充要条件是S中某个字符的数目超过了(|S|+1)/2。
换句话说，除非有一个字母数量 过多，否则一定可以有一个合法的重排方案。
例如样例"aaabc"，5个字符中有3个'a'。这个例子'a'的数量就在临界值上，我们必须在第1、3、5个位置上都放'a'才能把所有的'a'分隔开。如果'a'的数量再多1个，比如"aaaabc"，那就没办法把'a'都分隔开了，结果就是INVALID。
那么，当我们知道目前的S不是INVALID时，我们怎么求字典序最小的重排方案呢？ 这里我们可以使用一个贪心策略：我们按照'a'-'z'的顺序枚举第一个字符c，如果除去c之后，S的剩余的字符仍然>不是INVALID，那么我们就把第一个字符定为c。之后我们可以用同样的策略确定第二位、第三位……，只是在确定第二位、第三位……的时候还需要要求当前字符不能与之前定下来的字符相同。
举个例子，假设S="bbbac"，我们知道出现最多的'b'一共出现了3次，没超过(|S|+1)/2=3，所以至少存在一种重排方案。这时我们要确定重排之后的第一个字符。由于我们希望字典序最小，所以我们 会先尝试第一个字符是'a'行不行。假设第一个字符是'a'，那么剩余的S'="bbbc"，这时剩余的S是INVALID，所以我们不能把'a'放在一个字符。
然后我们再尝试把'b'放在第一个字符。这时剩余的S'是"bbac"，我们知道"bbac"至少存在一个解，并且这个解不需要第一个字符一定是'b'(因为如果S'的解需要第一个字符一定是某个ch，那么S=S'+ch一定INVALID，大家可以仔细想想）。所以我们可以安全的令第一个字符是'b'，一定是字典序最小的选择。
同样的贪心策略处理3个字符后之后，我们就会得到前3个字符是："bab"，这时余下的字符是"bc"。注意由于前一个字符是'b'，所以此时字典序的第一选择'b'不能被选（尽管出去'b'之后剩余字符仍 然有解），所以第四个字符选'c'。
最终我们得到答案："babcb"。
本题的关键就是每一个字符选择时，都需要判断剩余字符有没有解。由于只有'a'-'z'26个字母，判断有没有解可以认为是O(26)=O(1)即常数复杂度的。所以总复杂度是O(|S|)。
c语言代码：
#include<stdio.h> #include<string.h> char s[100010]; int az[27]; char work(int x,int y,char a) { int i,j,k,l; j=0; k=y/2; l=y%2; for(i=0;i<26;i++) { if(az[i]>k+l) { return ' '; }else if(az[i]==k+l) { if(l==1) { s[x]=i+'a'; az[i]--; return i+'a'; } /*else { j=0; while(az[j]==0 || j+'a'==a)j++; s[x]=j+'a'; az[j]--; return j+'a'; }//*/ } } j=0; while(az[j]==0 || j+'a'==a)j++; s[x]=j+'a'; az[j]--; return j+'a'; } int main() { int i,j,k,l,L; char c; while(gets(s)!=NULL) { L=l=strlen(s); memset(az,0,sizeof(az)); for(i=0;i<l;i++)az[s[i]-'a']++; //for(j=0;j<26;j++)if(az[j]>0)printf("%c%d ",j+'a',az[j]); //printf(" "); k=0; c=' '; for(i=0;i<L;i++) { c=work(i,l,c); l--; if(c==' ')k=1; //for(j=0;j<26;j++)if(az[j]>0)printf("%c%d ",j+'a',az[j]); //printf(" "); } if(k==0)printf("%s ",s);else printf("INVALID "); } return 0; }
c++代码：
#include<iostream> #include<cstring> char s[100010]; int letters[27]; using namespace std; char deal_str(int num,int l,char c) { int max,i,j,k; i=l%2; max=(l+1)/2; for(k=0;k<26;k++){ if(letters[k]>max){ return ' '; }else if(letters[k]==max){ if(i==1){ s[num]=k+'a'; letters[k]--; return k+'a'; } } } j=0; while(letters[j]==0 || j+'a'==c){ j++; } s[num]=j+'a'; letters[j]--; return j+'a'; } int main(){ int i,n,l,err; char c; while(cin>>s){ n=l=strlen(s); memset(letters, 0, sizeof(letters)); for(i = 0; i < n; ++i){ letters[s[i] - 'a']++; } err=0; c=' '; for(i=0;i<n;i++) { c=deal_str(i,l,c); l--; if(c==' '){ err = 1; } } if(err==0){ cout<<s<<endl; }else { cout<<"INVALID"<<endl;; } } return 0; }
c语言代码：
#include<stdio.h>
#include<string.h>
char s[100010];
int az[27];
char work(int x,int y,char a)
{
int i,j,k,l;
j=0;
k=y/2;
l=y%2;
for(i=0;i<26;i++)
{
if(az[i]>k+l)
{
return ' ';
}else if(az[i]==k+l)
{
if(l==1)
{
s[x]=i+'a';
az[i]--;
return i+'a';
}
/*else
{
j=0;
while(az[j]==0 || j+'a'==a)j++;
s[x]=j+'a';
az[j]--;
return j+'a';
}//*/
}
}
j=0;
while(az[j]==0 || j+'a'==a)j++;
s[x]=j+'a';
az[j]--;
return j+'a';
}
int main()
{
int i,j,k,l,L;
char c;
while(gets(s)!=NULL)
{
L=l=strlen(s);
memset(az,0,sizeof(az));
for(i=0;i<l;i++)az[s[i]-'a']++;
//for(j=0;j<26;j++)if(az[j]>0)printf("%c%d ",j+'a',az[j]);
//printf("
");
k=0;
c=' ';
for(i=0;i<L;i++)
{
c=work(i,l,c);
l--;
if(c==' ')k=1;
//for(j=0;j<26;j++)if(az[j]>0)printf("%c%d ",j+'a',az[j]);
//printf("
");
}
if(k==0)printf("%s
",s);else printf("INVALID
");
}
return 0;
}
c++代码：
#include<iostream>
#include<cstring>
char s[100010];
int letters[27];
using namespace std;
char deal_str(int num,int l,char c)
{
int max,i,j,k;
i=l%2;
max=(l+1)/2;
for(k=0;k<26;k++){
if(letters[k]>max){
return ' ';
}else if(letters[k]==max){
if(i==1){
s[num]=k+'a';
letters[k]--;
return k+'a';
}
}
}
j=0;
while(letters[j]==0 || j+'a'==c){
j++;
}
s[num]=j+'a';
letters[j]--;
return j+'a';
}
int main(){
int i,n,l,err;
char c;
while(cin>>s){
n=l=strlen(s);
memset(letters, 0, sizeof(letters));
for(i = 0; i < n; ++i){
letters[s[i] - 'a']++;
}
err=0;
c=' ';
for(i=0;i<n;i++)
{
c=deal_str(i,l,c);
l--;
if(c==' '){
err = 1;
}
}
if(err==0){
cout<<s<<endl;
}else {
cout<<"INVALID"<<endl;;
}
}
return 0;
}