前排提示:
- 前两道很简单,所有人都必须熟练掌握。
- 第三题直接暴力枚举$O(n^2)$也能拿不少分数。
- 基础好的同学建议掌握:利用归并排序求逆序对的方法。
- 类似题目还有acwing算法基础课中的785、786题:利用快速排序求数组中第k个数。
1. 覆盖点集
输入若干个点的坐标x, y,其中x, y 都是正整数。当输入0,0时表示输入结束。现要求输入完毕以后,输出一个长方形左下角和右上角的坐标。要求长方形区域覆盖所有输入点坐标。
算法思想:
1. 初始化最小和最大坐标为整数最大值和整数最小值。
2. 通过循环读取输入的坐标,更新最小和最大的 x 和 y 坐标。
3. 当输入遇到 (0, 0) 时,表示输入结束,输出长方形的左下角和右上角坐标。
#include <iostream>
#include <climits>
using namespace std;
int main() {
int x, y;
int min_x = INT_MAX, min_y = INT_MAX;
int max_x = INT_MIN, max_y = INT_MIN;
while (true) {
// 读取输入的坐标
cin >> x >> y;
// 判断是否输入结束
if (x == 0 && y == 0) {
break;
}
// 更新最小和最大坐标
min_x = min(min_x, x);
min_y = min(min_y, y);
max_x = max(max_x, x);
max_y = max(max_y, y);
}
// 输出长方形左下角和右上角坐标
cout << "Left Bottom: (" << min_x << ", " << min_y << ")" << endl;
cout << "Right Top: (" << max_x << ", " << max_y << ")" << endl;
return 0;
}
输入样例:
1 2
3 4
5 6
0 0
输出样例:
Left Bottom: (1, 2)
Right Top: (5, 6)
2. 回文串
回文串可以被定义为形如 abccba,也可以是 a bc cb a。
(1) 使用递归思想,实现一个可以检测回文串的函数。
(2)不使用递归,使用栈来实现上述功能
算法思想:
(1) 递归检测回文串:
- 如果字符串的长度为0或1,它是回文串。
- 否则,检查字符串的最左边和最右边的字符是否相等,然后递归地检查去除最左和最右字符后的子串。
(2) 栈实现检测回文串:
- 使用栈将字母推入栈。
- 从左到右遍历字符串,将字母推入栈。
- 再次从左到右遍历字符串,与从栈中弹出的字符进行比较。如果任何字符不匹配,返回 false;否则,返回 true。
#include <iostream>
#include <stack>
using namespace std;
// (1) 递归检测回文串
bool isPalindromeRecursive(string str, int start, int end) {
// 基本情况:如果子串长度为0或1,它是回文串
if (start >= end)
return true;
// 递归情况:检查最外层字符是否相等
if (str[start] == str[end])
// 移到下一个内层子串
return isPalindromeRecursive(str, start + 1, end - 1);
// 如果最外层字符不相等,它不是回文串
return false;
}
// (2) 栈实现检测回文串
bool isPalindromeWithStack(string str) {
stack<char> charStack;
// 将每个字母推入栈
for (char ch : str)
charStack.push(ch);
// 与从栈中弹出的字符进行比较
for (char ch : str) {
if (ch != charStack.top())
return false;
charStack.pop();
}
return true;
}
int main() {
string input;
cout << "输入一个字符串: ";
getline(cin, input);
// 使用递归检测回文串
if (isPalindromeRecursive(input, 0, input.size() - 1))
cout << "使用递归: 是回文串。" << endl;
else
cout << "使用递归: 不是回文串。" << endl;
// 使用栈检测回文串
if (isPalindromeWithStack(input))
cout << "使用栈: 是回文串。" << endl;
else
cout << "使用栈: 不是回文串。" << endl;
return 0;
}
输入样例:
输入一个字符串: a bc cb a
输出样例:
使用递归: 是回文串。
使用栈: 是回文串。
输入样例:
输入一个字符串: Hello, World!
输出样例:
使用递归: 不是回文串。
使用栈: 不是回文串。
3. 逆序对的数量
给定一个长度为 n 的整数数列,请你计算数列中的逆序对的数量。
逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i]>a[j],则其为一个逆序对;否则不是。
输入格式
第一行包含整数 n ,表示数列的长度。
第二行包含 n 个整数,表示整个数列。
输出格式
输出一个整数,表示逆序对的个数。
数据范围
1≤n≤100000,
数列中的元素的取值范围 $[1,10^9]$。
输入样例:
6
2 3 4 5 6 1
输出样例:
5
利用归并排序:$O(nlogn)$
算法思想:
- 使用归并排序的思想,在归并的过程中统计逆序对的数量。
- 分别对左半部分和右半部分进行递归排序,并在合并的过程中计算逆序对数量。
- 在合并的过程中,当左半部分的元素大于右半部分的元素时,说明找到了一个逆序对,逆序对的数量为 mid - i + 1。
- 将两个有序部分合并成一个有序数组。
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, q[N], w[N];
// 归并排序并统计逆序对数量
LL merge_sort(int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (q[i] <= q[j]) w[k++] = q[i++];
else {
res += mid - i + 1;
w[k++] = q[j++];
}
}
while (i <= mid) w[k++] = q[i++];
while (j <= r) w[k++] = q[j++];
// 将合并后的有序数组复制回原数组
for (int i = l, j = 0; j < k; i++, j++) q[i] = w[j];
return res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> q[i];
// 输出逆序对数量
cout << merge_sort(0, n - 1) << endl;
return 0;
}
补充:归并排序代码
算法思想:
- 使用归并排序算法,将数组分为左右两部分,递归地对左右两部分进行排序。
- 将排序好的左右两部分进行合并,得到最终的有序数组。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
// n: 输入元素个数, q: 存储输入元素的数组, w: 辅助数组用于归并排序
int n, q[N], w[N];
// 归并排序函数
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = l + r >> 1; // 取中点
merge_sort(l, mid); // 递归排序左半部分
merge_sort(mid + 1, r); // 递归排序右半部分
int i = l, j = mid + 1, k = 0;
// 归并排序的合并操作
while (i <= mid && j <= r) {
if (q[i] <= q[j])
w[k++] = q[i++];
else
w[k++] = q[j++];
}
// 处理剩余元素
while (i <= mid) w[k++] = q[i++];
while (j <= r) w[k++] = q[j++];
// 将辅助数组的排序结果复制回原数组
for (int i = l, j = 0; j < k; i++, j++) q[i] = w[j];
}
int main() {
// 输入数据
cin >> n;
for (int i = 0; i < n; i++) cin >> q[i];
// 归并排序
merge_sort(0, n - 1);
// 输出结果
for (int i = 0; i < n; i++) cout << q[i] << ' ';
return 0;
}
暴力做法 $O(n^2)$
算法思想:
- 使用双重循环暴力遍历所有可能的逆序对。
- 对于每一对元素 (q[i], q[j]),如果满足 q[i] > q[j],则说明找到了一个逆序对,逆序对的数量 res 加 1。
- 最终输出逆序对的数量。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, q[N];
int main() {
// 输入数据
cin >> n;
for (int i = 0; i < n; i++) cin >> q[i];
int res = 0; // 逆序对数量
// 使用双重循环暴力遍历所有可能的逆序对
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (q[i] > q[j]) res++;
// 输出结果
cout << res << endl;
return 0;
}
原题链接:AcWing 788. 逆序对的数量
这个19年的难度不小呀哈哈哈
送分