acwing week2 基础算法3总结
acwing week2 基础算法3总结总结点1：双指针算法
//常用模版框架
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作题1：最长连续不重复子序列
我们用指针i指向子序列的终点，j指向子序列的起点。
每次指针i后移时，这个序列中重复的那个数只可能是s,所以我们判断一下s出现的次数是否大于1，
如果大于1，说明子序列中s这个数重复了，那么就更新答案和起点，继续循环。
判断出现的次数，我们用数组a做标记。
代码：
#include using namespace std;int n;const int N = 100010;int s, a;int main(){ cin >> n; for (int i = 0; i < n; i++) { cin >> s; } int ans = 0; for (int i = 0, j = 0; i < n; i++)//i指向终点，j指向起点 { a]++;//新加值的次数+1； while (j < i && a]>1)//如果重复(a]>1) 就更新起点，直到a] == 1; { a]--;//删除数的次数-- j++;//起点指针后移 } ans = max(ans, i - j + 1);//更新答案 } coutn >> m >> x; for (int i = 0; i < n; i++) { cin >> a; } for (int i = 0; i < m; i++) { cin >> b; } for (int i = 0, j = m - 1; i < n; i++) { while (a + b > x) { j--; } if (a + b == x) { coutm; for (int i = 0; i < n; i++) { cin >> a; } for (int i = 0; i < m; i++) { cin >> b; } int ans = 0; for (int i = 0, j = 0; i < n&&j n >> m; for (int i = 0; i < n; i++) { int x, c; cin >> x >> c; add.push_back({ x, c }); //x是需要用到的坐标 alls.push_back(x); } for (int i = 0; i < m; i++) { int x, c; cin >> x >> c; query.push_back({ x,c }); alls.push_back(x); alls.push_back(c); } //对alls数组进行排序并去重 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); //将原坐标对应的数据，储存到新坐标中 for (int i = 0; i < n; i++) { int x = find(add.first); a += add.second; } //前缀和模版 for (int i = 1; in; for (int i = 0; i < n; i++) { int l, r; cin >> l >> r; segs.push_back({ l,r }); } merge(segs); cout
页:
[1]