描述
给定一个只包含小写字母’a’-‘z’的字符串 S ，你需要将 S 中的字符重新排序，使得任意两个相同的字符不连在一起。
如果有多个重排后字符串满足条件，输出字典序最小的一个。
如果不存在满足条件的字符串，输出INVALID。
输入
字符串S。(1 ≤ |S| ≤ 100000)
输出
输出字典序最小的答案或者INVALID。
样例输入
aaabc
样例输出
abaca
限制
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
思路
贪心，由题意易知VALID的充要条件即为此字母的长度小于整个字符串长度len/2向上取整。在每次贪心之后重新check新字符串是否VALID就可。
题解
C++
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| /*
Author: Yuki
GitHub: https://github.com/Yuki-14544869/
Blog: https://yuki-14544869.github.io/
*/
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int min = 0x3f3f3f3f;
#define ff(a, b, c, d) for(int a=b; a<c; a+=d)
#define mm(a, b) memset(a, b, sizeof(a))
string input;
int cnt[26] = {0};
bool check(int x) {
ff(i, 0, 26, 1)
if(cnt[i]>(x-1)/2+1)
return false;
return true;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
cin >> input;
int len = input.size();
//cout << len << endl;
ff(i, 0, len, 1)
cnt[input[i]-'a']++;
if(!check(len)) {
cout << "INVALID" << endl;
return 0;
}
/*
int pre = -1;
ff(i, 0, len, 1) {
ff(j, 0, 26, 1) {
if(cnt[j]>0 && j!=pre) {
cnt[j]--;
if(check(len-1)) {
putchar('a'+j);
pre = j;
len--;
break;
} else cnt[j]++;
}
}
}
*/
int pre = -1;
ff(i, 0, input.size(), 1) {
ff(j, 0, 26, 1) {
if(cnt[j] && j!=pre) {
cnt[j]--;
if(check(len-1)) {
putchar('a'+j);
pre=j;
len--;
break;
}
else cnt[j]++;
}
}
}
cout << endl;
return 0;
}
|
Java
