知识点为双指针。
AcWing 1238. 日志统计（蓝桥杯辅导课）
题目描述
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 \(N\) 行。
其中每一行的格式是：
ts id
表示在 \(ts\) 时刻编号 \(id\) 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 \(D\) 的时间段内收到不少于 \(K\) 个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 \(T\) 满足该帖在 \([T,T+D)\) 这段时间内(注意是左闭右开区间)收到不少于 \(K\) 个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 \(N,D,K\)。
以下 \(N\) 行每行一条日志，包含两个整数 \(ts\) 和 \(id\)。
输出格式
按从小到大的顺序输出热帖 \(id\)。
每个 \(id\) 占一行。
数据范围
\(1≤K≤N≤10^5,\)
\(0≤ts,id≤10^5,\)
\(1≤D≤10000\)
输入样例
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例
1
3
解题思路
双指针+滑动窗口。我们维护一个区间长度为 \(D\) 的区间，统计该区间内的“热帖”，利用 \(cnt\) 数组，实现点赞数的更新，这个技巧在AcWing 799. 最长连续不重复子序列这道题中也有使用。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
#define x first
#define y second
int n, d, k;
PII logs[N];
int cnt[N];
bool st[N];
int main()
{
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 ++)
{
// printf("%d %d\n", logs[i].x, logs[i].y);
cnt[logs[i].y] ++; // 点赞数+1
while (logs[i].x - logs[j].x >= d) // 时间间隔>=d
{
cnt[logs[j].y] --;
j ++;
}
if (cnt[logs[i].y] >= k) st[logs[i].y] = true;
}
for (int i = 0; i < N; i ++)
if (st[i])
printf("%d\n", i);
return 0;
}
AcWing 1240. 完全二叉树的权值（蓝桥杯辅导课）
题目描述
给定一棵包含 \(N\) 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 \(A_1,A_2,...,A_N\)，如下图所示：
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？
如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 \(1\)。
输入格式
第一行包含一个整数 \(N\)。
第二行包含 \(N\) 个整数 \(A_1,A_2,...,A_N\)。
输出格式
输出一个整数代表答案。
数据范围
\(1≤N≤10^5,\)
\(−10^5≤A_i≤10^5\)
输入样例
7
1 6 5 4 3 2 1
输出样例
2
解题思路
题目要求我们得到层的权值和最小的层数，那么最直接的一个思路，计算每一层的和，比较得到最小层的层数。数据范围是 \(N=10^5\)，那么最多有 \(logN\) 层，每个节点只遍历一次，算法的时间复杂度应为 \(O(NlogN)\)。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int n, a[N];
vector<int> v[15];
int get(int x)
{
int ans = 1;
for(int i = 1; i <= x; i ++)
ans *= 2;
return ans;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
int i, j;
for(i = 1, j = 1; i <= n;)
{
while(i <= n && i <= get(j) - 1 && i >= get(j - 1))
{
v[j].push_back(a[i ++]);
}
j ++;
}
//cout << i << " " << j << endl;
j --;
LL sum = -1e18, ans = 0;
for(int k = 1; k <= j; k ++)
{
LL cnt = 0, len = v[k].size();
for(int t = 0; t < len; t ++)
cnt += v[k][t];
if(sum < cnt)
{
sum = cnt;
ans = k;
}
//cout << len << endl;
}
printf("%lld\n", ans);
return 0;
}