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