前言
蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十一讲：双指针【例/习题】
本篇博客所包含习题有：
👊日志统计
👊完全二叉树的权值
👊递增三元组
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
日志统计
来源： 第九届蓝桥杯省赛C++B组,第九届蓝桥杯省赛JAVAB组
题目要求
题目描述：
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。
其中每一行的格式是：
ts id
输入格式：
第一行包含三个整数 N , D , K 。
以下 N 行每行一条日志，包含两个整数 t s 和 i d 。
输出格式：
按从小到大的顺序输出热帖id。
每个 i d占一行。
数据范围：
输入样例：
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例：
1
3
思路分析
代码
#include <cstdio> #include <cstring> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 100010; PII logs[N]; int cnt[N]; bool st[N]; int main() { int n, d, k; scanf("%d%d%d", &n, &d, &k); for (int i = 0; i < n; i ++ ) scanf("%d%d", &logs[i].x, &logs[i].y); sort(logs, logs + n); for (int i = 0, j = 0; i < n; i ++ ) { int id = logs[i].y; cnt[id] ++; while (logs[i].x - logs[j].x >= d) { cnt[logs[j].y] --; j ++; } if (cnt[id] >= k) st[id] = true; } for (int i = 0; i <= 100000; i ++ ) if (st[i]) printf("%d\n", i); return 0; }
完全二叉树的权值
来源： 第十届蓝桥杯省赛C++A/B组,第十届蓝桥杯省赛JAVAA组
题目要求
题目描述：
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是A1,A2,⋅⋅⋅AN，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？
如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是1。
输入格式：
第一行包含一个整数 N 。
第二行包含 N 个整数A1,A2,⋅⋅⋅AN。
输出格式：
输出一个整数代表答案。
数据范围：
1≤N≤105,
−105≤Ai≤105
输入样例：
7
1 6 5 4 3 2 1
输出样例：
2
思路分析
我们一层一层的去遍历，对于构造一个完全二叉树，我们可以按照如下进行构造：
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010; int a[N]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); LL Max = -1e18; int depth = 0; for (int d = 1, i = 1; i <= n; i *= 2, d ++ ) //遍历每一层 { LL temp = 0; for (int j = i; j < i + (1 << d - 1) && j <= n; j ++ ) temp += a[j]; if (temp > Max) { Max = temp; depth = d; } } printf("%d\n", depth); return 0; }
递增三元组
来源： 第九届蓝桥杯省赛C++B组,第九届蓝桥杯省赛JAVAB组
题目要求
题目描述：
给定三个整数数组
A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],
请你统计有多少个三元组 ( i , j , k ) 满足：
1≤i,j,k≤N
Ai<Bj<Ck
输入格式：
第一行包含一个整数 N。
第二行包含 N 个整数A1,A2,…AN。
第三行包含 N 个整数B1,B2,…BN。
第四行包含 N 个整数C1,C2,…CN。
输出格式：
一个整数表示答案。
数据范围：
1≤N≤105,
0≤Ai,Bi,Ci≤105
输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27
思路分析
本题有三种解法，本博客只讲解双指针的解法，对于前缀和、二分的解法见博客：蓝桥杯第八讲–枚举与模拟【例题】
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010; int n; int a[N], b[N], c[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]); for (int i = 0; i < n; i ++ ) scanf("%d", &b[i]); for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]); sort(a, a + n); sort(b, b + n); sort(c, c + n); LL res = 0; for (int i = 0, j = 0, k = 0; j < n; j ++ ) { while (i < n && a[i] < b[j]) i ++; while (k < n && c[k] <= b[j]) k ++; res += (LL)i * (n - 1 - k + 1); } printf("%lld\n", res); return 0; }
