EOJ Monthly 2017.12

EOJ Monthly 2017.12"/>

EOJ Monthly 2017.12

Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

易位构词 (anagram)，指将一个单词中的字母重新排列，原单词中的每个字母都出现有且仅有一次。例如 "unce" 可以被易位构词成 "ecnu"。在某些情况下，要求重排而成的依然是一个单词，但本题没有这种要求，因为我们根本没有词典。

我们所感兴趣的是，有些单词中的字母进行适当的重排后，可以使得构成的单词每个对应的位置上字母都不一样。例如 "unce" 和 "ecnu"，就有 "u"  ≠  "e", "n"  ≠  "c", "c"  ≠  "n", "e"  ≠  "u"。现在给出一个单词，问是否存在这样一个重排。

Input

一行一个单词  s  ( 1≤|s|≤105 )。单词完全由  26  个小写英文字母构成。

Output

输出一个单词。如果有多解，输出任意解。如果不存在，输出 impossible。

Examples

unce

ecnu

aaaaaa

impossible

出现次数最多的字母的次数若大于l/2，则为im。

然后就乱搞。可以贪心给字符。

但到最后可能会有空字符。  譬如abc   按照我的贪心思路。 答案为ba。 c因为和c矛盾，就没了。

所以空字符的那些继续贪心和前面的交换。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn  = 1e5+55;
int main()
{char s[maxn];int num[222];while(~scanf("%s",s)){int Max=0;memset(num,0,sizeof num);int l=strlen(s);for(int i=0;i<l;i++){num[s[i]]++;Max=max(Max,num[s[i]]);}if(Max>l/2){printf("impossible\n");continue;}int ans[maxn];memset(ans,0,sizeof  ans);int now=0;for(int i=0;i<l;i++){for(int j='a';j<='z';j++){if(num[j]>0&&j!=s[i]){ans[i]=j;num[j]--;now++;break;}}}while(now<l){int k=-1;for(int i=0;i<l;i++){if(ans[i]==0){k=i;break;}}for(int i=0;i<l;i++){if(ans[i]!=s[k]&&s[k]!=s[i]){ans[k]=ans[i];ans[i]=s[k];break;}}now++;}for(int i=0;i<l;i++){printf("%c",ans[i]);}printf("\n");}
}