Codeforces 915C(思维)

Codeforces 915C
题意:给出两个数$a,b$,求出$a$重排后不超过$b$的最大值。
现将$a$进行排序,然后如果$a$的位数比$b$小,则直接倒过来输出$a$即可。
否则,就暴力看每个位置放哪个数。取最相近的是最优的,之后再从大到小输出没有取的即可。但是会有以下情况
$a=127986,b=127111$
答案会变成$127986$,不对。怎么办?
用check检测一下取的相等的时候是否能够继续放下去,那么就可以过了
ps: 千万不要在for里面改循环变量,很容易错

Codeforces Submission

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
string a, b, ans;
int lena, lenb, pos, used[30];
bool check() {
string taki;
for (int i = 0; i < lena; i++) if (!used[i]) taki += a[i];
int len = taki.length();
for (int i = 0; i < len; i++) {
if (taki[i] > b[i + pos + 1]) return 1;
if (taki[i] < b[i + pos + 1]) return 0;
}
return 0;
}
void clean() {
pos = 0;
ms(used, 0);
}
int solve() {
clean();
lena = a.length(), lenb = b.length();
sort(a.begin(), a.end());
if (lenb > lena) return reverse(a.begin(), a.end()), cout << a, 0;
for (int i = lena - 1; i >= 0; i--) {
if (used[i]) continue;
if (a[i] < b[pos]) {
ans += a[i], pos++, used[i] = true;
break;
} else if (a[i] == b[pos]) {
used[i] = true;
if (check()) {
used[i] = false;
continue;
}
ans += a[i], pos++, i = lena;//小心i--, 以后循环里面不要改值,不然用while
}
}
for (int i = lena - 1; i >= 0; i--) if (!used[i]) ans += a[i];
cout << ans;
return 0;
}
int main() {
cin >> a >> b, solve();
return 0;
}

------ 本文结束 ------