这次比赛做得乱七八糟,事实上一共只做出来两道题,结果rating还涨了一点点,看来确实有点难。。

1117A

题目来源:https://codeforces.com/contest/1117/problem/A

提交次数:1/1

题意

给定一个数组,问数组中满足平均数最大的前提下长度最长的子数列。

分析

就是找到最大值然后计算最大值最多连续出现了多少次而已。水题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int n;
int a[100005];
int main() {
int maxn = -1;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
maxn = max(maxn, a[i]);
}
int ans = 0, l = 1;
for (int i = 1; i <= n; i++) {
if (i == n || a[i] != a[i - 1]) {
if (a[i - 1] == maxn) ans = max(l, ans);
l = 1;
}
else l++;
}
cout << ans << endl;
return 0;
}

1117B

题目来源:https://codeforces.com/contest/1117/problem/B

提交次数:1/1

题意

给定n个emote,每个emote可以将对手的快乐值增加a[i],你可以使用一些emote共m次,相同的emote最多连续使用k次,问最多能增加多少快乐值?

分析

找出值最大和值次大的emote,连续用最大的emotek次,用一次次大的emote,再接着用最大的emote,以此类推,直到一共用了m次为止。水题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n, m, k;
LL a[200005];
int main() {
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
LL cnt = m / (k + 1);
LL ans = cnt * (a[n-1] * k + a[n-2]) + (m - (k + 1) * cnt) * a[n-1];
cout << ans << endl;
return 0;
}

1117C

题目来源:https://codeforces.com/contest/1117/problem/C

提交次数:1/4

题意

你在(x1, y1)处有一艘船,每天可以向上或下、左、右移动1格。每天的移动效果会和天气效果叠加,天气效果会使得船根据风向往上或下、左、右移动一格。给定m天的天气,之后的天气是循环的,问最少需要几天,船才能到达(x2, y2)处?

分析

比赛的时候我意识到走完一个天气循环之后,能到的位置是一个菱形了(或者说是一个尖朝上的正方形);但很可惜我没有意识到这件事的本质,还打算拿计算几何来做(??)。显然,这件事的本质是这样的:把天气推船走的路和船自己走的路分开,可以得出一个结论:天气在一个循环内推船走的路是固定的,不妨记为(dx, dy);船自己可以在这个点周围走出一个菱形,或者说是所有满足|x-dx|+|y-dy|<=n的点。所以对天数二分查找就好了。当然,还是需要重视一下二分查找的前提:只要x天能到,那么y>=x天也能到。(大不了不动)[1]

除此之外就是注意上界。显然如果能到达(x2, y2),每个天气循环至少要向这个方向前进1格(曼哈顿距离),所以上界是(|x2-x1| + |y2-y1|)*n。如果走了这么多还没到,说明到不了了。

代码

因为long long int的使用错了好多次……

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL x1, y1, x2, y2;
int n;
char s[100005];
pair<LL, LL> pos[100005];
LL fx, fy;
// U, R, D, L
int mx[4] = {0, 1, 0, -1};
int my[4] = {1, 0, -1, 0};

bool isOk(LL days) {
LL sx = (days / n) * fx, sy = (days / n) * fy;
sx += pos[days % n].first, sy += pos[days % n].second;
return abs(x2 - sx) + abs(y2 - sy) <= days;
}

int main() {
cin >> x1 >> y1 >> x2 >> y2;
x2 -= x1;
y2 -= y1;
cin >> n;
cin >> s;
for (int i = 1; i <= n; i++) {
int d;
if (s[i-1] == 'U') d = 0;
else if (s[i-1] == 'R') d = 1;
else if (s[i-1] == 'D') d = 2;
else if (s[i-1] == 'L') d = 3;
pos[i].first = pos[i-1].first + mx[d];
pos[i].second = pos[i-1].second + my[d];
}
fx = pos[n].first, fy = pos[n].second;

LL l = 0, r = (abs(x2) + abs(y2)) * n;
while (l < r) {
LL m = (l + r) / 2;
if (isOk(m)) r = m;
else l = m + 1;
}
if (!isOk(l)) cout << -1 << endl;
else cout << l << endl;
return 0;
}

1117D

题目来源:https://codeforces.com/contest/1117/problem/D

提交次数:1/1

题意

一颗魔法宝石可以分裂成M颗普通宝石,问有多少种选择魔法宝石的方法,使得分裂后总的宝石数量是N?不同的魔法宝石数量和不同index的分裂被认为是不同的方法。N<=10^18M<=100

分析

比赛的时候我努力推了一个公式出来:

$$\sum_{i=0}^{\lfloor N/M \rfloor} \binom{N-(M-1)i}{i}$$

但是肯定不能这么算,因为N太大了。我心想:用动态规划估计也不行。

事实上得用到动态规划递推的思路,看到NM的大小,我早该想到是矩阵快速幂才对。

f[n]表示N=n时的方法数量。显然有两种方法进行递推:一种是加上一块不分裂的宝石(f[n-1]);另一种是加上一块分裂的宝石(f[n-M])。(虽然第二维看起来没有什么意义……)考虑到递推的本质,不需要乘新加的宝石的位置,因此:

1
f[n] = f[n-1] + f[n-M]

现在就可以造一个矩阵乘法迭代公式了:

1
2
3
4
5
| f[n-M]  f[n-M+1]  ...  f[n-1] | * | 0 0 0 ... 0 1 | = | f[n-M+1] |
| 1 0 0 ... 0 0 | | f[n-M+2] |
| 0 1 0 ... 0 0 | | ... |
| 0 0 1 ... 0 0 | | f[n-1] |
| 0 0 0 ... 1 1 | | f[n] |

然后矩阵快速幂即可。

太久没写矩阵快速幂,手都生了……

代码

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
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
LL N;
int M;

const LL P = 1000000007;

struct Matrix {
int n, m;
LL a[105][105];

Matrix(int _n, int _m) {
memset(a, 0, sizeof(a));
n = _n;
m = _m;
}

friend Matrix operator * (const Matrix& m1, const Matrix& m2) {
Matrix m3(m1.n, m2.m);
for (int i = 1; i <= m1.n; i++)
for (int j = 1; j <= m1.m; j++)
for (int k = 1; k <= m2.m; k++)
m3.a[i][k] = (m3.a[i][k] + m1.a[i][j] * m2.a[j][k]) % P;
return m3;
}

void print() {
cout << n << ' ' << m << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
cout << a[i][j] << ' ';
cout << endl;
}
}
};

Matrix getIdentity(int n) {
Matrix mat(n, n);
for (int i = 1; i <= n; i++)
mat.a[i][i] = 1;
return mat;
}

int main() {
cin >> N >> M;
if (N < M) {
cout << 1 << endl;
return 0;
}
Matrix v(1, M);
for (int i = 1; i < M; i++)
v.a[1][i] = 1;
v.a[1][M] = 2;

Matrix x(M, M);
for (int i = 2; i <= M; i++)
x.a[i][i - 1] = 1;
x.a[1][M] = x.a[M][M] = 1;

LL delta = N - M;
Matrix pow = x;
Matrix ans = getIdentity(M);
while (delta > 0) {
if (delta & 1) ans = ans * pow;
delta >>= 1;
pow = pow * pow;
}
v = v * ans;
cout << v.a[1][M] << endl;
return 0;
}

1117E

题目来源:https://codeforces.com/contest/1117/problem/E

提交次数:1/1

题意

这是一道交互题。给定一个字符串,已知对它进行了<=n次swap操作;你可以拿出一个新的和它长度一样的字符串,然后得到对这个字符串进行相同的swap之后的结果。你最多可以提交三次字符串。问原来的字符串是多少?

分析

比赛的时候,我看了看这道题……觉得很有趣,但应该想半天也做不出来吧。(我从来没在比赛里做对过交互题)这道题的一种解法是这样的:既然每次提交的字符串的swap操作是一样的,不妨把提交的三次字符串看成是一个字符串,它的每个位置是由三个字符组成的一个“超字符”。这样我们就可以认为每个位置的“超字符”是两两不等的了!因为26^3 = 17576 >= 1e4,这是可行的。

然后就可以立即得到每个输入位置到输出位置的映射了,倒过来对原来的字符串重新做一遍就行了。

评论区里还出现了用中国剩余定理的做法,我没细看。[2]

代码

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
#include <iostream>
#include <cstring>
using namespace std;

char s[10005];
char q[3][10005];
char a[3][10005];
int mapping[10005];
int n;

int main() {
cin >> s;
n = strlen(s);
int m = 0;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
for (int k = 0; k < 26; k++) {
q[0][m] = i + 'a';
q[1][m] = j + 'a';
q[2][m] = k + 'a';
m++;
if (m >= n) break;
}
if (m >= n) break;
}
if (m >= n) break;
}
for (int i = 0; i < 3; i++) {
cout << "? " << q[i] << endl;
cin >> a[i];
}
for (int i = 0; i < n; i++) {
int idx = (a[0][i] - 'a') * 26 * 26 + (a[1][i] - 'a') * 26 + (a[2][i] - 'a');
mapping[idx] = i;
}
cout << "! ";
for (int i = 0; i < n; i++)
cout << s[mapping[i]];
cout << endl;
return 0;
}

1117F

题目来源:https://codeforces.com/contest/1117/problem/F

提交次数:?/?

题意

还没看懂,感觉有点难度。

111G

题目来源:https://codeforces.com/contest/1117/problem/G

提交次数:?/?

题意

给定一个由1到n的全排列组成的数组,记m[l, r]范围内的最大元素index,定义函数

1
2
f(l, r) = (r - l + 1) + f(l, m - 1) + f(m + 1, r) (l <= r)
f(l, r) = 0 (l > r)

给定q个询问,请给定f的值。

1 <= n, q <= 1e6

分析

这道题我比赛的时候自然是不会做的。比赛完了,看看题解,发现也晦涩难懂。[1]

首先需要把f分解成两个函数,flfr

1
2
3
fl(l, r) = (m - l) + fl(l, m-1) + fl(m+1, r)
fr(l, r) = (r - m) + fr(l, m-1) + fr(m+1, r)
f(l, r) = (r - l + 1) + fl(l, r) + fr(l, r)

可以用数学归纳法简单地证明这个分解的正确性(虽然我可不知道为什么要这样分解……):

1
2
3
4
5
f(l, r) = (r - l + 1) + fl(l, r) + fr(l, r)
= (r - l + 1) + fl(l, m-1) + fl(m+1, r) + (m - l)
+ fr(l, m-1) + fr(m+1, r) + (r - m)
= (r - l + 1) + f(l, m-1) - (m-1 - l + 1) + f(m+1, r) - (r - (m+1) + 1) + (r - l)
= (r - l + 1) + f(l, m-1) + f(m+1, r)

然后不妨举一个例子来看看fl是怎么算出来的:

fl的例子

(显然fl(i, i) = fr(i,i) = 0

把这些式子全部展开,就会变成:

1
2
3
4
fl(1, 6) = (3-1) + fl(1, 2) + fl(4, 6)
= (3-1) + (1-1) + fl(2, 2) + (4-4) + fl(5, 6)
= (3-1) + (1-1) + (2-2) + (4-4) + (6-5) + fl(5, 5)
= (3-1) + (1-1) + (2-2) + (4-4) + (6-5) + (5, 5)

可以看出,fl其实是由6项组成的,而且每一项都是某个l <= i <= r与它左边最近的比它小的元素(或者l)之间的距离。这么想其实很合理。记i左边离它最近的比它大的元素为lf[i],可以看出,它对fl(l, r)产生贡献当且仅当它被作为最大元素选中了,且贡献大小为min(i - l, i - lf[i] - 1)


  1. Educational Codeforces Round 60 Editorial

  2. saeed_odak's comment for 1117E

题目来源:https://codeforces.com/contest/1102/problem/F

提交次数:2/3

题意

给定一个n1<=n<=16)行m列的矩阵,重新排列矩阵的各行,使得逐列遍历矩阵时相邻两个数之差绝对值的最小值最大。

分析

还是一道状态压缩DP。首先计算出每两行之间的距离(注意第一行和最后一行的距离)。

然后对于每种状态,枚举可能的起始结点,最大化路径上边权重的最小值。状态总数是n * 2^n(末尾结点*状态总数),枚举起始结点的代价为O(n),枚举上一个结点的代价是O(n),总计算复杂度是O(n^3 * 2^n)。如果不用递归还要多一个O(n),不知道有没有解决这个问题的方法。

另一种比较神奇的方法是二分答案,然后在图上寻找回路。题解里的具体方法是这样的:枚举起始点i,对于每个点j,寻找一条从ij的经过了所有结点的路径,然后再判断ji是否有路径。题解[1]里这种方法的复杂度是O(n^2 * log(MAXN) * 2^n)。但是我并不会题解里的写法,所以我写出来的还是平凡的O(n^3 * 2^n)的求哈密顿回路法……

代码

迭代写法的DP

相当慢……

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
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int a[16][10000];
int nextOk[16][16];
int firstLastOk[16][16];
int f[16][16][1 << 16];
int n, m, k;
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x = 1e9;
for (int k = 0; k < m; k++) {
x = min(x, (int) abs(a[i][k] - a[j][k]));
if (x == 0) break;
}
nextOk[i][j] = nextOk[j][i] = x;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x = 1e9;
for (int k = 1; k < m; k++) {
x = min(x, (int) abs(a[j][k-1] - a[i][k]));
if (x == 0) break;
}
firstLastOk[i][j] = x;
}
}

if (n == 1) {
cout << firstLastOk[0][0] << endl;
return 0;
}

int ans = 0;
// 枚举路径长度
for (int len = 1; len <= n; len++) {
for (int status = 0; status < (1 << n); status++) {
if (__builtin_popcount(status) != len) continue;
for (int first = 0; first < n; first++) {
if (!(status & (1 << first))) continue;
if (len == 1) {
f[first][first][status] = 1e9;
continue;
}
for (int cur = 0; cur < n; cur++) {
if (!(status & (1 << cur)) || first == cur) continue;
f[first][cur][status] = 0;
for (int last = 0; last < n; last++) {
if (!(status & (1 << last)) || cur == last) continue;
int x = min(f[first][last][status ^ (1 << cur)], nextOk[last][cur]);
if (len == n) x = min(x, firstLastOk[first][cur]);
f[first][cur][status] = max(f[first][cur][status], x);
}
if (len == n) ans = max(f[first][cur][status], ans);
}
}
}
}
cout << ans << endl;
return 0;
}

递归写法的DP+二分答案

因为常数写多了所以甚至更慢了……

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
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
int a[16][10000];
int nextOk[16][16];
int firstLastOk[16][16];
int f[16][1 << 16];
bool g[16][16];
int n, m, k;

int calc(int x, int state) {
if (f[x][state] != -1) return f[x][state];
f[x][state] = 0;
for (int i = 0; i < n; i++) {
if (i != x && (state & (1 << i)) && g[i][x] && calc(i, state ^ (1 << x))) {
f[x][state] = 1;
break;
}
}
return f[x][state];
}

bool isOk(int thres) {
memset(g, 0, sizeof(g));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && nextOk[i][j] >= thres)
g[i][j] = true;
}
}

for (int i = 0; i < n; i++) {
memset(f, -1, sizeof(f)); // 因为这句memset位置错了,调了一阵子
// 控制只能从i开始
for (int j = 0; j < n; j++)
f[j][1 << j] = j == i ? 1 : 0;
for (int j = 0; j < n; j++) {
if (firstLastOk[i][j] >= thres) {
if (calc(j, (1 << n) - 1)) return true;
}
}
}
return false;
}

int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x = 1e9;
for (int k = 0; k < m; k++) {
x = min(x, (int) abs(a[i][k] - a[j][k]));
if (x == 0) break;
}
nextOk[i][j] = nextOk[j][i] = x;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x = 1e9;
for (int k = 1; k < m; k++) {
x = min(x, (int) abs(a[j][k-1] - a[i][k]));
if (x == 0) break;
}
firstLastOk[i][j] = x;
}
}

if (n == 1) {
cout << firstLastOk[0][0] << endl;
return 0;
}

// 二分答案
// 这个写法是从题解里抄的(感觉也不是很优雅啊)
// <del>谁叫你也写不出优雅的</del>
int l = 0, r = 1e9;
while (l < r - 1) {
int m = (l + r) >> 1;
if (isOk(m)) l = m;
else r = m;
}
if (isOk(r)) cout << r << endl;
else cout << l << endl;
return 0;
}

  1. Codeforces Round #531 (Div. 3) Editorial

题目来源:https://leetcode.com/problems/find-peak-element/description/

标记难度:Medium

提交次数:2/2

代码效率:

  • 线性扫描:8ms
  • 二分查找:4ms

题意

给定一个数组,其中任意两个相邻元素不等,请返回其中一个peak元素(即比两边元素都大;可以认为nums[-1]=nums[n]=+inf)。

要求代码时间复杂度为O(log(n))

分析

线性扫描的方法太简单了,不值得细说。不过在写的时候很容易想到一个很有趣的问题:在题设条件下是否保证有这样的peak元素出现呢?我觉得显然是有的。不妨利用反证法:假设这样的peak元素不存在,则对于nums[0]nums[n-1],由于它们旁边各有一个比它们小的元素(nums[-1]nums[n]),为了保证peak元素不存在,必有nums[0] < nums[1]nums[n-2] > nums[n-1]。然后以此类推,即可推出矛盾。

通过上述方法大概可以想到一种二分的思路。选择i = n/2,判断是否满足nums[i-1] < nums[i] > nums[i+1]

  • 如果满足,则显然i就是满足要求的peak元素
  • 否则,如果nums[i-1] < nums[i] < nums[i+1],则必存在一个peak元素位于[i+1, n-1]范围中
  • 如果nums[i-1] > nums[i] > nums[i+1],则必存在一个peak元素位于[0, i-1]范围中
  • 如果nums[i-1] > nums[i] < nums[i+1],则i两侧都可能存在peak元素

代码

线性扫描

1
2
3
4
5
6
7
8
9
class Solution {
public:
int findPeakElement(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++)
if ((i == 0 || nums[i] > nums[i-1]) && (i == nums.size() - 1 || nums[i] > nums[i+1]))
return i;
return -1;
}
};

二分查找

参考了题解[1]的写法……题解的细节写得还是挺不错的。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int findPeakElement(vector<int>& nums) {
if (nums.size() == 1) return 0;
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1]) r = mid;
else l = mid + 1;
}
return l;
}
};

  1. Leetcode Offcial Solution for 162. Find Peak Element

题目来源:https://leetcode.com/problems/random-pick-with-blacklist/description/

标记难度:Hard

提交次数:3/6

代码效率:

  • 二分:10.06%
  • 重映射:45.67%

题意

给定区间[0, N)和一个该区间内的“黑名单”,要求以均匀的概率返回该区间内非黑名单的数字,且调用rand()的次数尽量少。

分析

二分

我感觉这是一道很妙的题。看到题之后,我的第一反应是:假定黑名单的长度为M,那么我们只需要随机[0, N - M)范围内的数字,然后把它们映射到[0, N)区间内就可以了。问题是怎么映射呢?

于是我想出了这样一种做法:随机得到一个数字之后,计算黑名单中有多少个数小于等于这个数,然后把这个数量加到这个数上,返回结果。然后我就把代码交上去了,于是,很快我就发现这个做法错得有点离谱,因为它完全没有保证返回的数不在黑名单里。反例如N = 4, blacklist = [0, 1],随机得到0时,上述做法会返回1。

于是我尝试从另一个角度来思考这个问题。我们显然可以显式地构建一个映射:顺序枚举[0, N - M)范围内的数,维护一个指针,指向下一个能够被映射的数,遇到黑名单中的数则跳过。这个做法是正确的,但考虑到1 <= N <= 1000000000的数据量,显然不可能把整个映射表都建立出来,然后去查表。

于是这个思路被否决了,我又回头去考虑怎么在线计算出准确的映射这个问题。我想了想:考虑“黑名单中有多少个数小于等于当前的数”这个思路其实是正确的,问题在于,被考虑的不应该是[0, N - M)中的数,而应该是[0, N)中的数。考察这个例子,N = 9, balcklist = [2, 3, 5],令blacklist_before(i)表示黑名单中<=i的数的个数:

[0, N)中的数i blacklist_before(i) i - blacklist_before(i) 映射到[0, N - M)
0 0 0 0
1 0 1 1
2 1 1 -
3 2 1 -
4 2 2 2
5 3 2 -
6 3 3 3
7 3 4 4
8 3 5 5

可以观察得到一些非常有趣的性质:

  • i - blacklist_before(i)是非单调递增的,因为它代表的是[0, i]区间内不属于黑名单内的数的个数
  • i - blacklist_before(i)没有递增时,表示i是一个黑名单内的数字
  • i[0, N - M)区间中应该映射到的数与i - blacklist_before(i)两列很接近(从意义上来说也是)

所以可以从这个逆向映射的角度考虑,用二分的方法解决问题:假定在[0, N - M)中随机得到了y,我们需要找到满足x - blacklist_before(x) == yxlower_bound。然后就可以写了。


在讨论区里我看到了类似的做法,但是思考的角度不太一样。我们可以把从区间[0, N - M)中生成随机数r的情形这样分类:[1]

  • r[0, B[0])区间内,可以直接返回r
  • r[B[0], B[1] - 1)区间内,应返回r + 1
  • ...
  • r[B[i]-i, B[i+1]-(i+1))区间内,应返回r + i + 1。注意到r + i + 1位于[B[i] + 1, B[i+1])区间内,因此这样做是安全的。

因此可以在B[i] - (i+1)数组中进行二分查找。

这种做法是在经过处理的blacklist数组上进行二分查找,而我是在[0, N)区间上直接查找,所以比我的做法更压缩一些。

HashMap重映射法

我之前考虑过建立整个映射表,但因为数据量而放弃了。然而,事实上,完全不需要把整个映射表都建立出来;或者不如说,完全不需要按顺序建立映射,只要保证所有数字都可以被随机取到即可。所以可以采取这样的一种做法:将黑名单中的元素分成两类,一类在[0, N - M)区间内,一类在[N - M, N)区间内。然后在[N - M, N)区间内为[0, N - M)区间内的黑名单元素顺序寻找映射(我看到了从前向后[2]和从后向前[3]两种方法,不过本质上是相同的),同时注意跳过那些同样在黑名单内的元素。

上述从后向前找映射的一个图示例子:N=10, blacklist=[3, 5, 8, 9],将3和5映射为7和6。

从后向前映射

代码

二分

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
class Solution {
private:
int N;
vector<int> blacklist;
unordered_set<int> blackSet;
random_device rd;
mt19937 gen;
uniform_int_distribution<> dist;

int findMap(int y) {
int l = 0, r = N - 1;
// need to find lower_bound
// 二分真是一件Tricky的事情
while (l < r) {
int mid = (l + r) / 2;
int smaller = upper_bound(blacklist.begin(), blacklist.end(), mid) - blacklist.begin();
if (mid - smaller < y)
l = mid + 1;
else
r = mid;
}

return l;
}

public:
Solution(int N, vector<int> blacklist): gen(rd()), dist(0, N - blacklist.size() - 1) {
this->N = N;
this->blacklist = blacklist;
sort(this->blacklist.begin(), this->blacklist.end());
for (int b: blacklist)
blackSet.insert(b);
}

int pick() {
int r = dist(gen);
int m = findMap(r);
// cout << r << ' ' << m << endl;
// 事实证明,保证lower_bound之后,找到的数必然不是黑名单中的数
/* while (blackSet.find(m) != blackSet.end())
m++; */
return m;
}
};

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(N, blacklist);
* int param_1 = obj.pick();
*/
// 这个问题很有趣。
// 既然从N个数的区间中屏蔽了B.length个点,那么就是从N - B.length的区间中随机选点
// 然后换算一下。
// 但是换算方法看起来是个很大的问题……

重映射

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
class Solution {
private:
int N;
vector<int> blacklist;
unordered_set<int> blackSet;
unordered_map<int, int> blackMap;
random_device rd;
mt19937 gen;
uniform_int_distribution<> dist;

public:
Solution(int N, vector<int> blacklist): gen(rd()), dist(0, N - blacklist.size() - 1) {
this->N = N;
this->blacklist = blacklist;
sort(this->blacklist.begin(), this->blacklist.end());
for (int b: blacklist)
blackSet.insert(b);

int M = blacklist.size();
int mapTo = N - M;
for (int b: this->blacklist) {
if (b >= N - M)
break;
while (blackSet.find(mapTo) != blackSet.end())
mapTo++;
blackMap[b] = mapTo++;
}
}

int pick() {
int r = dist(gen);
if (blackSet.find(r) != blackSet.end())
return blackMap[r];
return r;
}
};

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(N, blacklist);
* int param_1 = obj.pick();
*/

  1. Simple Java solution with Binary Search

  2. Java O(B) constructor and O(1) pick, HashMap

  3. Java O(B) / O(1), HashMap

题目来源:https://leetcode.com/problems/heaters/description/

标记难度:Easy

提交次数:1/1

代码效率:18.81%

题意

x轴上有若干个暖气和若干个房子,每个暖气能够覆盖到半径为x的圆内的房子,问至少取x为多少,才能覆盖所有房子。(所有暖气的半径是一样的)

分析

如果需要排序,则时间复杂度下限应该是$O(n \log{n})$。排序之后,很显然可以立刻利用二分查找(lower_boundupper_bound)来寻找距离每所房子最近的暖气,并确定所需的最小半径。如果房子和暖气开始时都是排好序的,则很显然有$O(n)$的解法,因为此时随着房子坐标的递增,它在暖气中的lower_bound必然也是单调递增的,因此扫描一遍所有暖气就够了,具体解法可参见C++ O(N) speed O(1) space

以及我每次都记不住upper_bound的用法。

  • 调用方法:upper_bound(vector.begin(), vector.end(), val)
  • 返回值:iterator(虽然这么说不算很准确)
  • 返回值使用方法:
    • *iteratorlower_bound的数值
    • iterator - vector.begin()lower_bound对应的数在数组中的下标
    • iterator != vector.end():是否找到了lower_bound

代码

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
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
// 既然标签是Easy,那我觉得大概是个贪心问题,至多是动态规划问题
// (当然这个思考方式是不好的)
// 又看错题了,原来所有的暖气的半径要求是一样的。
// 我感觉有O(n)的解法,但是显然直接O(n * log(n))比较方便。

if (houses.size() <= 0 || heaters.size() <= 0)
return 0;

int n = houses.size(), m = heaters.size();
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());

// 我决定为每一个房子找到离它最近的暖气。
int ans = 0;
for (int i = 0; i < n; i++) {
auto ub = upper_bound(heaters.begin(), heaters.end(), houses[i]);
int dist;
// 此house的坐标>=所有heater的坐标
if (ub == heaters.end())
dist = houses[i] - heaters[m-1];
else {
int j = ub - heaters.begin();
dist = heaters[j] - houses[i];
if (j > 0)
dist = min(dist, houses[i] - heaters[j-1]);
}
ans = max(ans, dist);
}

return ans;
}
};