二分、前缀和与差分

写在前面

二分答案和差分构造上我一直是苦手,写这一篇存档记录一下可用的模板。

Problem1

描述:

给定升序排列数组 \(a[n]\) 以及 \(q\) 个查询,每次查询 \(k\) 在数组中的起始位置。

题解:

二分查找,贴一个模板还有一个暴力(前者45ms,后者39ms)

模板:

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
#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N];
int n, q;

int main()
{
cin >> n >> q;
for(int i = 1; i <= n; i ++) scanf("%d", a + i);
while(q--)
{
int k;
scanf("%d", &k);
int l = 1, r = n;
while(l < r)// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
{
int mid = l + r >> 1;
if(a[mid] >= k)
{
r = mid;
}
else
{
l = mid + 1;
}
}
if(a[l] != k)
{
printf("-1 -1\n");
continue;
}
else
{
printf("%d ", l - 1);
r = n;
while(l < r)// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
{
int mid = l + r + 1 >> 1;
if(a[mid] <= k) l = mid;
else r = mid - 1;
}
printf("%d\n", r - 1);
}
}
}

暴力

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
#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N];
int n, q;

int main()
{
cin >> n >> q;
for(int i = 1; i <= n; i ++) scanf("%d", a + i);
while(q--)
{
int k;
scanf("%d", &k);
int l = 1, r = n;
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] >= k)
{
r = mid;
}
else
{
l = mid + 1;
}
}
if(a[l] != k)
{
printf("-1 -1\n");
continue;
}
else
{
for(r = l; r <= n && a[r] == k; r ++);
printf("%d %d\n", l - 1, r - 2);
}
}
}

Problem2

描述:

输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标,对于每个询问输出子矩阵中所有数的和。

题解:

二维前缀和模板,举个例子画一下就知道怎么做了

模板:

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;

int a[N][N], s[N][N];
int n, m, q;

int main()
{
cin >> n >> m >> q;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= m; j ++)
{
scanf("%d", &a[i][j]);
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
int x1, y1, x2, y2;
while(q--)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
printf("%d\n", ans);
}
}

Problem3

描述:

输入一个长度为n的整数序列,接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c,输出进行完所有操作后的序列。

题解:

一维差分模板,构造数组 \(b[n]\) ,使其满足 \(a[i]\)\(b[i]\) 的前缀和

你当然可以用线段树解决

模板:

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
#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N], b[N];
int n, m;

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
scanf("%d", a + i);
b[i] = a[i] - a[i - 1];
}

int l, r, c;
while(m --)
{
scanf("%d%d%d", &l, &r, &c);
b[l] += c;
b[r + 1] -= c;
}

for(int i = 1; i <= n; i ++)
{
b[i] = b[i] + b[i - 1];
printf("%d ", b[i]);
}
return 0;
}

Problem4 机器人跳跃问题

描述:

字节跳动2019校招题,此处代码为\(O(nlogn)\)的二分,还有更优的\(O(n)\)算法下面链接自取

https://www.nowcoder.com/questionTerminal/7037a3d57bbd4336856b8e16a9cafd71

题解:

第一想法就是二分答案,但是被右边界坑了两发,check函数竟然最终会爆long long,所以只要超过范围就直接返回即可。

Code:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;

ll n, h[N];

bool check(ll x)
{
for(int i = 1; i <= n; i ++)
{
x += x - h[i];
if(x < 0) return false;
if(x > N) return true;
}
return true;
}

int main()
{
scanf("%lld", &n);
for(int i = 1; i <= n; i ++) scanf("%lld", h + i);

ll l = 0, r = N;
while(l < r)
{
ll mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}

cout<<l<<endl;
}
----- 本文结束 感谢阅读 -----
0%