建设一个淘宝客网站/谷歌seo价格

第十四章 基础算法与数据结构

AcWing 1506. 中位数

问题描述

• 问题链接：AcWing 1506. 中位数、原题链接

  

分析

• 基本做法：使用归并排序的归并操作将两个有序数组归并为一个有序数组c，然后输出c的中位数即可。

• 另外本题还有一个log(n+m)的做法，对应题目是Leetcode 0004 寻找两个正序数组的中位数。

• 对于给定的数组A、B，我们要找到这两个数组中的中位数，我们考虑一个更加一般的问题，如何找到第k小的数据。

• 假设我们需要找到A[i...]和B[j...]这两个数组的第k小的数据，则我们可以比较 $A[i+\lfloor \frac{k}{2}\rfloor -1]$ 和 $B[j+\lfloor \frac{k}{2}\rfloor -1]$ 的大小，则会存在三种情况：

  （1） $A[i+\lfloor \frac{k}{2}\rfloor -1]\le B[j+\lfloor \frac{k}{2}\rfloor -1]$ ：说明 $A[i...i+\lfloor \frac{k}{2}\rfloor -1]$ 都不可能是第k小的数，这是因为即使$B[j...j+\lfloor \frac{k}{2}\rfloor -2]$都小于$A[i+\lfloor \frac{k}{2}\rfloor -1]$的话，$A[i+\lfloor \frac{k}{2}\rfloor -1]$也只是第k-1小的数，因此可以被删除；

  （2） $A[i+\lfloor \frac{k}{2}\rfloor -1]>B[j+\lfloor \frac{k}{2}\rfloor -1]$ ：说明 $B[j...j+\lfloor \frac{k}{2}\rfloor -1]$ 都不可能是第k小的数，同理也可以被删除；

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v6phdFCq-1630636811035)(14 第十四章 基础算法与数据结构.assets/image-20210731215907805.png)]

• 下面的代码中让：$newI=i+\lfloor \frac{k}{2}\rfloor -1$，$newJ=j+\lfloor \frac{k}{2}\rfloor -1$。

代码

• C++

#include <iostream>using namespace std;const int N = 200010;int n, m;
int a[N], b[N], c[N * 2];int main() {scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);scanf("%d", &m);for (int i = 0; i < m; i++) scanf("%d", &b[i]);int k = 0, i = 0, j = 0;while (i < n && j < m)if (a[i] <= b[j]) c[k++] = a[i++];else c[k++] = b[j++];while (i < n) c[k++] = a[i++];while (j < m) c[k++] = b[j++];printf("%d\n", c[(m + n - 1) / 2]);return 0;
}

#include <iostream>using namespace std;const int N = 200010;int n, m;
int a[N], b[N];// 在两个有序数组 a 和 b 中获取第k小(从1开始)的数据
int get(int k) {int i = 0, j = 0;while (true) {if (i == n) return b[j + k - 1];if (j == m) return a[i + k - 1];if (k == 1) return min(a[i], b[j]);int newI = min(i + k / 2, n) - 1;int newJ = min(j + k / 2, m) - 1;if (a[newI] < b[newJ]) {k -= (newI - i + 1);i = newI + 1;} else {k -= (newJ - j + 1);j = newJ + 1;}}
}int main() {scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);scanf("%d", &m);for (int i = 0; i < m; i++) scanf("%d", &b[i]);printf("%d\n", get((m + n + 1) / 2));return 0;
}

AcWing 1530. 最短距离

问题描述

• 问题链接：AcWing 1530. 最短距离、原题链接

  

分析

• 任意两个位置有两条路径，取较小的那个路径即可。

• 首先把这个环变为链，然后考虑如何计算两个距离，如下图：

代码

• C++

#include <iostream>using namespace std;const int N = 100010;int n, m;
int s[N];int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {int x;scanf("%d", &x);s[i] = s[i - 1] + x;}scanf("%d", &m);while (m--) {int l, r;scanf("%d%d", &l, &r);if (l > r) swap(l, r);printf("%d\n", min(s[r - 1] - s[l - 1], s[n] - s[r - 1] + s[l - 1]));}return 0;
}

AcWing 1571. 完美序列

问题描述

• 问题链接：AcWing 1571. 完美序列、原题链接

  

分析

• 本题相当于让我们找到一个子集，这个子集的元素满足最大值小于等于最小值的p倍。

• 首先将数组从小到大排序，则最优结果一定是一段区间。

• 我们可以枚举区间最大值a[i]，然后找到满足条件的最小的j满足a[i]<=a[j]*p，此时该区间长度为i-j+1，用该长度更新最终答案即可。

• 因为随着i的增加j也是单调增加的，因此可以使用滑动窗口解决该问题。

代码

• C++

#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n, p;
int a[N];int main() {scanf("%d%d", &n, &p);for (int i = 0; i < n; i++) scanf("%d", &a[i]);sort(a, a + n);int res = 0;for (int i = 0, j = 0; i < n; i++) {while (j < n && a[i] > (long long)a[j] * p) j++;res = max(res, i - j + 1);}printf("%d\n", res);return 0;
}

AcWing 1581. 急性中风

问题描述

• 问题链接：AcWing 1581. 急性中风、原题链接

  

分析

• floodfill算法，注意这里只能使用bfs，使用dfs在PAT上不能通过（因为栈空间给的不足）。

代码

• C++

#include <iostream>
#include <queue>using namespace std;const int M = 1286, N = 128, L = 60;int m, n, l, T;
int g[L][M][N];
struct Node {int x, y, z;
};int d[][3] = {{1, 0, 0},{-1, 0, 0},{0, 1, 0},{0, -1, 0},{0, 0, 1},{0, 0, -1},
};int bfs(int x, int y, int z) {queue<Node> q;q.push({x, y, z});int cnt = 1;while (q.size()) {auto t = q.front();q.pop();g[t.x][t.y][t.z] = 0;for (int i = 0; i < 6; i++) {int a = t.x + d[i][0], b = t.y + d[i][1], c = t.z + d[i][2];if (a >= 0 && a < l && b >= 0 && b < m && c >= 0 && c < n && g[a][b][c]) {q.push({a, b, c});g[a][b][c] = 0;cnt++;}}}return cnt;
}int main() {scanf("%d%d%d%d", &m, &n, &l, &T);for (int i = 0; i < l; i++)for (int j = 0; j < m; j++)for (int k = 0; k < n; k++)scanf("%d", &g[i][j][k]);int res = 0;for (int i = 0; i < l; i++)for (int j = 0; j < m; j++)for (int k = 0; k < n; k++)if (g[i][j][k]) {int t = bfs(i, j, k);if (t >= T) res += t;}printf("%d\n", res);return 0;
}

AcWing 1641. 狼人杀-简单版

问题描述

• 问题链接：AcWing 1641. 狼人杀-简单版、原题链接

  

分析

• 枚举所有可能的狼组合，然后判断给定的条件是否成立即可。

代码

• C++

#include <iostream>using namespace std;const int N = 110;int n;
int q[N];int judge(int k, int i, int j) {  // 如果是假话，返回1；如果是真话，返回0int t = q[k];if (t > 0) {if (t == i || t == j) return 1;return 0;}t = -t;if (t == i || t == j) return 0;return 1;
}int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> q[i];for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++) {  // 枚举狼人是(i, j)int s = judge(i, i, j) + judge(j, i, j);if (s != 1) continue;  // 有且只有一只狼在说谎 不成立s = 0;for (int k = 1; k <= n; k++)s += judge(k, i, j);if (s != 2) continue;  // 有 2 人说的不是实话 不成立cout << i << ' ' << j << endl;return 0;}puts("No Solution");return 0;
}

AcWing 1535. 弹出序列

问题描述

• 问题链接：AcWing 1535. 弹出序列、原题链接

  

分析

• 本题和Leetcode 0946 验证栈序列一样。

• 创建一个栈stk，每次向栈中插入一个元素，使用一个指针j指向出栈序列，初始为0，然后判断栈顶元素是否和当前考察的出栈序列中元素相同。

• 如果相同，弹栈，然后j++，直到栈空或者栈顶元素和当前考察的出栈序列的元素不相等。

• 最后如果栈非空，则说明不是合法序列，否则是合法序列。另外还要判断在操作过程中栈的空间是否足够使用。

代码

• C++

#include <iostream>
#include <stack>using namespace std;const int N = 1010;int m, n, k;
int q[N];bool check() {stack<int> stk;for (int i = 1, j = 0; i <= n; i++) {stk.push(i);if (stk.size() > m) return false;while (stk.size() && stk.top() == q[j]) stk.pop(), j++;}return stk.empty();
}int main() {scanf("%d%d%d", &m, &n, &k);while (k--) {for (int i = 0; i < n; i++) scanf("%d", &q[i]);if (check()) puts("YES");else puts("NO");}return 0;
}

AcWing 1541. 世界首富

问题描述

• 问题链接：AcWing 1541. 世界首富、原题链接

  

分析

• 统计出每个年龄段的人，放到一个容器中，然后对每个年龄段的人排序。

• 对于每个查询[a, b]，使用多路归并求解出年龄在a、b之间的前cnt个人输出即可。

• 多路归并标准的做法是使用优先队列，本题为了方便，直接遍历每个序列当前考察的元素，找到最大的一个即可。

代码

• C++

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>using namespace std;const int N = 210;int n, m;
struct Person {string name;int age, w;bool operator< (const Person &t) const {if (w != t.w) return w > t.w;if (age != t.age) return age < t.age;return name < t.name;}
};vector<Person> ages[N];
int idx[N];  // 存储多路归并中每路中考察的位置int main() {scanf("%d%d", &n, &m);char name[10];for (int i = 0; i < n; i++) {int age, w;scanf("%s%d%d", name, &age, &w);ages[age].push_back({name, age, w});}for (auto &age : ages) sort(age.begin(), age.end());for (int C = 1; C <= m; C++) {printf("Case #%d:\n", C);int cnt, a, b;scanf("%d%d%d", &cnt, &a, &b);memset(idx, 0, sizeof idx);bool exist = false;while (cnt--) {int t = -1;for (int i = a; i <= b; i++)if (idx[i] < ages[i].size()) {if (t == -1 || ages[i][idx[i]] < ages[t][idx[t]])  // 因为我们重载了<, 因此这里使用小于号t = i;}if (t == -1) break;  // 说明此年龄段已经没人了auto &p = ages[t][idx[t]];idx[t]++;printf("%s %d %d\n", p.name.c_str(), p.age, p.w);exist = true;}if (!exist) puts("None");}return 0;
}

AcWing 1543. 栈

问题描述

• 问题链接：AcWing 1543. 栈、原题链接

  

分析

• 本题的考点：对顶堆。类似的题目：Leetcode 0295 数据流的中位数。

• 与LC295不同的是本题还需要支持删除操作，因此需要使用multiset实现对顶堆。

• 对于Push操作：

  （1）如果down为空或者x小于等于down堆顶元素时，向down中插入数据x，并调整down和up，保证down中元素和up中元素个数相同或者多一个；

  （2）否则down非空并且x大于down堆顶元素，则向up中插入数据x，并调整down和up，保证up中元素个数和不能多于up中元素个数。

• 对于Pop操作：如果栈中无元素，则非法；否则从栈中删除一个元素x，然后找到x在的位置（down或者up），从中删除x，然后调整down、up元素个数。

• 对于PeekMedian操作，如果栈非空，返回down中最大元素即可。

代码

• C++

#include <iostream>
#include <cstring>
#include <stack>
#include <set>using namespace std;stack<int> stk;
multiset<int> up, down;void adjust() {if (up.size() > down.size()) {down.insert(*up.begin());up.erase(up.begin());}if (down.size() > up.size() + 1) {auto it = down.end();it--;up.insert(*it);down.erase(it);}
}int main() {int n;scanf("%d", &n);char op[20];while (n--) {scanf("%s", op);if (strcmp(op, "Push") == 0) {int x;scanf("%d", &x);stk.push(x);if (down.empty() || x <= *(--down.end())) down.insert(x);else up.insert(x);adjust();} else if (strcmp(op, "Pop") == 0) {if (stk.empty()) puts("Invalid");else {int x = stk.top();stk.pop();printf("%d\n", x);auto it = down.end();it--;if (x <= *it) down.erase(down.find(x));else up.erase(up.find(x));adjust();}} else {if (stk.empty()) puts("Invalid");else {auto it = down.end();it--;printf("%d\n", *it);}}}return 0;
}

AcWing 1607. 爱丁顿数

问题描述

• 问题链接：AcWing 1607. 爱丁顿数、原题链接

  

分析

• 本题和Leetcode 0274 H指数一样。

• 首先我们将数组从小达到排序，然后从n递减开始验证是否满足答案即可。

• 本题一定存在答案，因为最差的结果是0。

代码

• C++

#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n;
int a[N];int main() {scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);sort(a, a + n);for (int i = n; i > 0; i--)if (a[n - i] > i) {printf("%d\n", i);return 0;}printf("%d\n", 0);return 0;
}

AcWing 1528. 火星购物

问题描述

• 问题链接：AcWing 1528. 火星购物、原题链接

  

分析

• 本题目标是找到大于等于M的最小区间和res，然后把区间和等于res的所有区间输出。

• 首先是确定res，可以使用双指针，我们枚举区间右端点i，当i增大的时候，区间左端点j不可能减小。

• 当确定res后，使用双指针找到所有区间和等于res的区间即可。

代码

• C++

#include <iostream>using namespace std;const int N = 100010, INF = 1e9;int n, m;
int s[N];  // 原序列的前缀和int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {int x;scanf("%d", &x);s[i] = s[i - 1] + x;}int res = INF;for (int i = 1, j = 0; i <= n; i++) {while (s[i] - s[j + 1] >= m) j++;if (s[i] - s[j] >= m) res = min(res, s[i] - s[j]);}for (int i = 1, j = 0; i <= n; i++) {while (s[i] - s[j + 1] >= m) j++;if (s[i] - s[j] == res) printf("%d-%d\n", j + 1, i);}return 0;
}

AcWing 1524. 最长回文子串

问题描述

• 问题链接：AcWing 1524. 最长回文子串、原题链接

  

分析

• 我们依次枚举字符串中的每个字母s[i]，然后让s[i]或者(s[i], s[i+1])为中心，向两边扩展，得到以该中心为回文串的大小。

• 本题和Leetcode 0005 最长回文子串相同。

代码

• C++

#include <iostream>using namespace std;int main() {string str;getline(cin, str);int res = 0;for (int i = 0; i < str.size(); i++) {int l = i - 1, r = i + 1;while (l >= 0 && r <= str.size() && str[l] == str[r]) l--, r++;res = max(res, r - l - 1);l = i, r = i + 1;while (l >= 0 && r <= str.size() && str[l] == str[r]) l--, r++;res = max(res, r - l - 1);}printf("%d\n", res);return 0;
}