一、时间复杂度分析
1.1 分析模型基础
在分析算法复杂度之前，必须了解以下概念：
- ：算法执行所需的时间与输入规模的关系。
C++算法
算法入门：时间复杂度与基础排序算法
本文介绍算法入门知识，涵盖时间空间复杂度分析、多种排序算法（冒泡、选择、插入、希尔、计数、归并、快速）、大整数运算、数组操作、双指针技巧、二分查找、质数筛法、前缀和与差分、链表栈队列实现以及 DFS BFS 搜索和贪心思想。文中提供 C++ 代码示例辅助理解。
本文介绍算法入门知识，涵盖时间空间复杂度分析、多种排序算法（冒泡、选择、插入、希尔、计数、归并、快速）、大整数运算、数组操作、双指针技巧、二分查找、质数筛法、前缀和与差分、链表栈队列实现以及 DFS BFS 搜索和贪心思想。文中提供 C++ 代码示例辅助理解。
在分析算法复杂度之前，必须了解以下概念：
常用表示法：
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}
排序是很实用的、常用的（几乎是必需品，只不过现在封装得很好，让你感觉不到）。
排序的学习可以让你了解一些算法的基本思想与操作技巧（暴力、比较、交换、分治、减治、空间换时间等）。
排序算法中最简单直观的。
思路：不断缩小范围确定当前范围内的最小/最大值，随后将最小/最大值与目标位置进行交换。那么每一趟筛选的行为就是选出第 n 个最小/最大值！
举例： 从小到大排序下方数字
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
void select_sort(int* arr, int n) {
for (int i = 0; i < n - 1; i++) {
int pos = i; // 假设认为当前范围最小值 pos 就是当前范围的第一个数
for (int j = i + 1; j < n; j++) {
if (arr[pos] > arr[j]) { // 发现当前范围更小的数
pos = j; // 记录这个数的下标
}
}
// 交换这俩数
int t = arr[i]; arr[i] = arr[pos]; arr[pos] = t;
}
}
int main(void) {
int n; cin >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
select_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
见名知意，冒泡就是说将目前第 n 个最大/最小的数，冒泡到顶端。如果顶端有了 k 个泡，那么就要排在 k 个泡之后成为第 k+1 个泡。
思路：由于每次冒泡都需要排在之前泡泡的后面，并且之前冒泡的数值肯定是合理的。所以缩小冒泡范围并把当前范围最小/最大的值，通过相邻元素两两交换最后冒泡到范围顶端。
举例： 从小到大排序下方数字
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
void bubble_sort(int* arr, int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;
}
}
}
}
int main(void) {
int n; cin >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
bubble_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
如果一个排序算法在排序后能够保持相等元素的原始相对顺序，那么这个算法就是稳定的。
[("Alice",90),("Bob",85),("Chris",90),("Dave",80)]
// 稳定排序的升序（Alice 和 Chris 都是 90 分，Alice 原本在 Chris 前面，排序后仍然在前面。）
[("Dave",80),("Bob",85),("Alice",90),("Chris",90)].
// 不稳定排序的升序（可能 Alice 就在 Chris 的后面）
[("Dave",80),("Bob",85),("Chris",90),("Alice",90)]
插入排序类似于两堆扑克牌，从无序列扑克牌堆里面选牌插入到有序扑克牌堆。
思路：将数组分为已排序和未排序两部分，每次从未排序部分取出第一个元素，在已排序部分找到合适的位置插入。
举例：从小到大排序下方数字
#include <iostream>
using namespace std;
int arr[50];
int main(void) {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
for (int i = 1; i < n; ++i) {
// 要插入的元素
int t = arr[i]; // 存起来
int j = i - 1; // 18 1 5 27 12
// 1 5 18 27 12
for (; j >= 0; --j) {
if (arr[j] > t) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = t;
}
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
return 0;
}
希尔排序是插入排序的改进版，通过分组（分治思想）让插入排序提高了效率。
思路：
希尔排序会有一种假象：让初学者误认为嵌套循环多就是速度慢的、进而忽略了有序序列对插入排序具体实现过程的影响。
举例：从小到大排序下方数字 [18, 1, 5, 27, 12, 9, 6, 15]
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
void shell_sort(int* arr, int n) {
for (int gap = n / 2; gap > 0; gap /= 2) { // 增量序列
for (int i = gap; i < n; i++) { // 对每个分组进行插入排序
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
int main(void) {
int n; cin >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
shell_sort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
核心思想：统计每个元素出现的次数，然后按顺序输出。
特点：
void countingSort(int arr[], int n) {
// 假设数据范围在 0 到 100 之间
int count[101] = {0};
// 统计每个元素出现的次数
for (int i = 0; i < n; i++) count[arr[i]]++;
// 按顺序填充原数组
int index = 0;
for (int i = 0; i <= 100; i++) {
while (count[i]--) {
arr[index++] = i;
}
}
}
归并排序：应用快慢指针与递归去解决排序问题的算法。
#include <iostream>
using namespace std;
// 5 4 3 2 1
void merge_sort(int* arr, int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
merge_sort(arr, l, mid);
merge_sort(arr, mid + 1, r);
int tmp[10];
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i] < arr[j]) tmp[k++] = arr[i++];
else tmp[k++] = arr[j++];
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];
for (i = l, k = 0; i <= r; ++i, ++k) {
arr[i] = tmp[k];
}
}
int main(void) {
int n;
int arr[10]; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
merge_sort(arr, 0, n - 1);
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
return 0;
}
快速排序：应用左右指针与递归去解决排序问题的算法。
#include <iostream>
using namespace std;
// 5 4 3 2 1
void quick_sort(int* arr, int l, int r) {
if (l >= r) return;
int x = arr[(l + r) / 2];
int i = l - 1, j = r + 1;
while (i < j) {
do i++; while (arr[i] < x);
do j--; while (arr[j] > x);
if (i < j) {
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
quick_sort(arr, l, j);
quick_sort(arr, j + 1, r);
}
int main(void) {
int n;
int arr[10]; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
quick_sort(arr, 0, n - 1);
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
return 0;
}
接下来，继续锻炼模拟思维。
何为大整数：通常指的是非常大的整数，其值远超常规数据类型（如 32 位或 64 位整数）能直接表示的范围。
意义：
大整数加法应该算是四个运算法则里，最好理解的了。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(void) {
string a, b; cin >> a >> b;
vector<int> A;
vector<int> B;
// 做倒置存入到 vector 中（倒置是因为比较好处理，可以不倒置）
for (int i = a.size() - 1; i >= 0; --i) {
A.push_back(a[i] - '0');
}
for (int i = b.size() - 1; i >= 0; --i) {
B.push_back(b[i] - '0');
}
/* 4321 765 */
int t = 0; // 维护进位值
vector<int> C; // 存储最后结果
for (int i = 0; i < A.size() || i < B.size(); ++i) {
if (i < A.size()) t += A[i]; // 有就加，该位没数就不加
if (i < B.size()) t += B[i];
C.push_back(t % 10); // 存储的是某个位的数
t /= 10; // 更新进位值
}
if (t > 0) C.push_back(t); // 若最后进位值还有，那么就属于进多了一位
for (int i = C.size() - 1; i >= 0; --i) {
cout << C[i];
}
return 0;
}
大整数减法会遇到负数问题的处理，还有前置 0。关键点在于这里~
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 必须要判断出 A、B 两个数谁更大
bool isMax(vector<int> A, vector<int> B) {
if (A.size() == B.size()) {
for (int i = A.size() - 1; i >= 0; --i) {
if (A[i] == B[i]) {
continue;
}
return A[i] > B[i];
}
return true;
} else {
return A.size() > B.size();
}
}
int main(void) {
string a, b; cin >> a >> b;
vector<int> A;
vector<int> B;
for (int i = a.size() - 1; i >= 0; --i) {
A.push_back(a[i] - '0');
}
for (int i = b.size() - 1; i >= 0; --i) {
B.push_back(b[i] - '0');
}
bool flag = isMax(A, B);
if (!flag) // 如果 B 比 A 大则将他们交换，因为我们要默认 A - B 进行模拟运算
{
vector<int> temp = A;
A = B;
B = temp;
}
int t = 0; // 借位
vector<int> C;
for (int i = 0; i < A.size() || i < B.size(); ++i) {
int num = -t;
if (i < A.size()) num += A[i];
if (i < B.size()) num -= B[i];
if (num < 0) {
t = 1;
num += 10;
} else {
t = 0;
}
C.push_back(num % 10);
}
while (C.size() > 1 && C[C.size() - 1] == 0) {
C.pop_back();
}
if (C.size() == 1 && C[0] == 0) {
cout << 0 << endl;
return 0;
}
if (!flag) cout << "-";
for (int i = C.size() - 1; i >= 0; --i) {
cout << C[i];
}
return 0;
}
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
string a, b; cin >> a >> b;
vector<int> A;
vector<int> B;
for (int i = a.size() - 1; i >= 0; --i) {
A.push_back(a[i] - '0');
}
for (int i = b.size() - 1; i >= 0; --i) {
B.push_back(b[i] - '0');
}
/* 4321 765 */
vector<int> C(1000005);
if (A.size() < B.size()) swap(A, B);
for (int i = 0; i < B.size(); ++i) {
int j = 0;
int t = 0;
for (; j < A.size(); ++j) {
int num = A[j] * B[i] + t;
int ret = num % 10;
t = num / 10;
C[i + j] += ret;
C[i + j + 1] += C[i + j] / 10;
C[i + j] = C[i + j] % 10;
}
if (t > 0) C[i + j] += t;
}
bool flag = true;
for (int i = A.size() + B.size(); i >= 0; --i) {
if (i > 0 && flag && C[i] == 0) {
continue;
}
if (flag && C[i] != 0) {
flag = false;
}
cout << C[i];
}
return 0;
}
除法这里用到了大整数减法。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// 比较两个大整数
bool isGreaterOrEqual(vector<int> A, vector<int> B) {
if (A.size() != B.size()) return A.size() > B.size();
for (int i = A.size() - 1; i >= 0; --i) {
if (A[i] != B[i]) return A[i] > B[i];
}
return true;
}
// 减法函数
vector<int> subtractBigInt(vector<int> A, vector<int> B) {
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || i < B.size(); ++i) {
int num = -t;
if (i < A.size()) num += A[i];
if (i < B.size()) num -= B[i];
if (num < 0) {
t = 1;
num += 10;
} else {
t = 0;
}
C.push_back(num % 10);
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
// 除法函数
pair<vector<int>, vector<int>> divideBigInt(vector<int> dividend, vector<int> divisor) {
vector<int> quotient;
vector<int> remainder = dividend;
if (!isGreaterOrEqual(remainder, divisor)) {
return {vector<int>{0}, remainder};
}
vector<int> current;
for (int i = remainder.size() - 1; i >= 0; --i) {
current.insert(current.begin(), remainder[i]);
while (current.size() > 1 && current.back() == 0) current.pop_back();
int q = 0;
while (isGreaterOrEqual(current, divisor)) {
current = subtractBigInt(current, divisor);
q++;
}
quotient.push_back(q);
}
reverse(quotient.begin(), quotient.end());
while (quotient.size() > 1 && quotient.back() == 0) quotient.pop_back();
return {quotient, current};
}
int main() {
string a, b; cin >> a >> b;
vector<int> A, B;
for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
for (int i = b.size() - 1; i >= 0; --i) B.push_back(b[i] - '0');
auto [quotient, remainder] = divideBigInt(A, B);
cout << "Quotient: ";
for (int i = quotient.size() - 1; i >= 0; --i) cout << quotient[i];
cout << "\nRemainder: ";
for (int i = remainder.size() - 1; i >= 0; --i) cout << remainder[i];
return 0;
}
int arr[50]; // 开辟足够大的数组
int arr[2] = {5}; // 比如现在有两个元素了，我们增加一个元素。那就是 为下标 2 赋值
// 通过覆盖元素实现删除
int arr[50] = {1, 2, 3, 4, 5};
// 起始位置为待删除元素位置 终止位置为最后元素位置
for (int i = 0; i < n; ++i) {
arr[i] = arr[i + 1];
}
// 由于删掉一个元素 所以长度 从 n => n - 1
for (int i = 0; i < n - 1; ++i) {
cout << arr[i] << " ";
}
arr[5] = 18; // 改就是重新赋值
cout << arr[5] << endl; // 直接访问即可
// 其实就是依赖于下标找到 A 和 B 然后进行 交换操作
int temp = arr[2]; arr[2] = arr[3]; arr[3] = temp;
// 这个主要用的是 与删除操作 元素覆盖逆着来的写法。
// 比如我们要把下标 3 的元素 插入到目前下标为 1 的前面
int t = arr[3];
for (int i = 3 - 1; i >= 1; --i) {
arr[i + 1] = arr[i]; // 这个元素覆盖就是从左往右覆盖的 (由于会覆盖掉待移动的元素，所以我们提前用 变量 t 存储起来了)
}
arr[1] = t; // 从下标 1 开始都整体往右移动了一位，所以我们只需要将 下标 1 位置重新赋值为 t 即可完成需求
// 比如我们要把下标 3 的元素 插入到目前下标为 1 的后面
int t = arr[3];
for (int i = 3 - 1; i > 1; --i) {
arr[i + 1] = arr[i]; // 这个元素覆盖就是从左往右覆盖的 (由于会覆盖掉待移动的元素，所以我们提前用 变量 t 存储起来了)
}
arr[1 + 1] = t;
动态数组是普通数组的增强版。
主要它是要实现以下几个扩展功能：
#include <iostream>
#include <cstring>
using namespace std;
template<typename T>
class DynamicArray {
private:
T* data;
size_t size;
size_t capacity;
// 扩容
void reserve(size_t new_capacity) {
if (new_capacity <= capacity) return;
T* new_data = new T[new_capacity]; // 分配新内存
for (size_t i = 0; i < size; i++) {
new_data[i] = data[i];
}
delete[] data; // 释放旧内存
data = new_data;
capacity = new_capacity;
}
public:
DynamicArray(size_t init_capacity = 4) : size(0), capacity(init_capacity > 0 ? init_capacity : 4) {
data = new T[capacity]; // 分配初始内存
}
// 析构函数（释放内存）
~DynamicArray() {
delete[] data;
}
void push_back(const T& elem) {
if (size >= capacity) {
reserve(capacity * 2);
}
data[size++] = elem; // size 就是下标 size++ 就是数量
}
void remove(size_t index) {
if (index >= size) {
throw out_of_range("index out of bounds");
return;
}
for (int i = index; i < size - 1; ++i) {
data[i] = data[i + 1];
}
data[size - 1].~T(); // 调用析构函数
size--; // 数量少了一个！
}
T& operator[](size_t index) {
if (index >= size) {
throw out_of_range("index out of bounds");
}
return data[index];
}
size_t get_size() const {
return size;
}
size_t get_capacity() const {
return capacity;
}
};
int main(void) {
DynamicArray<int> arr;
arr.push_back(12);
for (int i = 0; i < arr.get_size(); i++) {
cout << arr[i] << " ";
}
return 0;
}
双指针严格来说不能是算法，它更像是一种技巧或思想。到后面的学习里，我们还会讲到贪心，它也是一种思想。双指针常被用于线性有单调性趋势遍历的优化之中！使其从 O(n^2) => O(n)。
概念：通过使用两个指针以不同的速度遍历数据结构（线性结构）。 —— 滑动窗口与快慢指针的思想就很类似。
检测链表是否有环 找链表中间节点 删除倒数第 N 个节点 判断是否为回文链表 寻找数组中重复元素
利用两者之间的速度差，可以在某个时刻根据特殊规则，获得或处理某些数据。
大白话：根据需求，当发现只需要用一个变量，先行一步拿到前置条件，再用另一个变量配合该前置条件，就可以完成需求时，那么你应该尝试下快慢指针。
#include <iostream>
using namespace std;
int arr[50];
int main(void) {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
if (n == 0) return 0; // 边界检查
int i = 0; // 慢指针（为了配合快指针的）
for (int j = 1; j < n; ++j) { // 快指针的目的是找到非重复项
if (arr[j] != arr[i]) {
// 找到之后，用非重复项覆盖掉重复项
i++;
arr[i] = arr[j]; // 覆盖重复项
}
}
// 输出去重后的数组（前 i+1 个元素）
for (int k = 0; k <= i; ++k) {
cout << arr[k] << " ";
}
cout << endl;
return 0;
}
原地删除某元素：比如数组 1,2,3,4,5,6,6,2,1,2,3,2 你就想把里面的 2 全部删掉。逆向思维去看，其实就是只保留不是 2 的元素。
#include <iostream>
using namespace std;
void remove_element(int arr[], int n, int val) {
int slow = 0;
for (int fast = 0; fast < n; ++fast) {
// 快指针去遍历
if (arr[fast] != val) {
// 进行筛选
arr[slow++] = arr[fast]; // 慢指针给数组重新赋值符合条件的 arr[fast]
}
}
}
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
int main(void) {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int maxLen = 0; // 记录最长长度
// n^3
// n^2
// 计数排序
// n
int cnt[maxN] = {0};
int i = 0; // 慢指针
for (int j = 0; j < n; ++j) {
cnt[arr[j]]++;
while (cnt[arr[j]] > 1) {
cnt[arr[i]]--;
i++;
}
if (maxLen < j - i + 1) maxLen = j - i + 1;
}
cout << maxLen << endl;
return 0;
}
左右指针是一种强大的算法技巧，其归属于双指针。特别适合处理数组和字符串问题。与快慢指针不同，左右指针同时从序列的两端向中间移动，形成 对称扫描！
左右指针最直接的应用就是：二分查找、二分法答案。
void two_pointers(int* arr, int n) {
int l = 0, r = n - 1; // r 是最后元素的下标
while (l < r) {
// 只要 l < r 就继续扫描
if 左侧条件满足 {
l++;
}
if 右侧条件满足 {
r--;
}
// 当然可能同时满足（这个所谓的条件，都是人为定的）
}
}
题目：给定一个已按非递减顺序排列的整数数组 numbers，请你从数组中找出两个数，它们的和等于目标数 target。假设每个输入只对应唯一的答案，并且不能使用相同的元素两次。
那么这道题。如果暴力去做，怎么样也得 O(n^2)。但由于题目说提供的数据是有序的，就可以利用左右指针优化到 O(n)。
void two_sum(int* arr, int n, int target) {
// 若升序，肯定遵循左小右大
int l = 0, r = n - 1;
while (l < r) {
int total = arr[l] + arr[r];
if (total == target) {
cout << l << " " << r << endl;
break;
} else if (total < target) {
// 证明左边的太小了
l++;
} else {
// 证明右边的太大了
r--;
}
}
cout << "" << endl;
}
题目：编写一个函数，将输入的字符串反转过来。
#include <iostream>
using namespace std;
int main(void) {
string a; cin >> a;
int i = 0, j = a.size() - 1;
while (i < j) {
char t = a[i]; a[i] = a[j]; a[j] = t;
i++; j--;
}
cout << a << endl;
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
int main(void) {
int n, x;
cin >> n >> x;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
if (arr[mid] > x) {
r = mid - 1;
} else if (arr[mid] < x) {
l = mid + 1;
} else {
cout << mid << endl;
return 0;
}
}
if (arr[l] == x) cout << l << endl;
else cout << -1 << endl;
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
int main(void) {
int n, x; cin >> n >> x;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (arr[mid] > x) {
r = mid - 1;
} else if (arr[mid] < x) {
l = mid + 1;
} else {
cout << mid << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
int main(void) {
int n, x; cin >> n >> x;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int l = 0, r = n - 1; // 1 2 2 2 3
while (l < r) {
int mid = (l + r) / 2;
if (arr[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
if (arr[l] == x) cout << l << endl;
else cout << -1 << endl;
l = 0, r = n - 1; // 1 2 2 2 3
while (l < r) {
int mid = (l + r + 1) / 2;
if (arr[mid] <= x) {
l = mid;
} else {
r = mid - 1;
}
}
if (arr[r] == x) cout << r << endl;
else cout << -1 << endl;
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
int main(void) {
int n, x; cin >> n >> x;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int l = 0, r = n - 1; // 1 2 2 2 3
while (l <= r) {
int mid = (l + r) / 2;
if (arr[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
if (arr[l] == x) cout << l << endl;
else cout << -1 << endl;
l = 0, r = n - 1; // 1 2 2 2 3
while (l <= r) {
int mid = (l + r) / 2;
if (arr[mid] > x) {
r = mid - 1;
} else {
l = mid + 1;
}
}
if (arr[r] == x) cout << r << endl;
else cout << -1 << endl;
return 0;
}
质数：只能被 1 与自身整除的数。
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
bool isPrime(int x) {
if (x <= 1) return false;
for (int i = 2; i < x; ++i) {
if (x % i == 0 && x != 2) {
return false;
}
}
return true;
}
int main(void) {
int n; cin >> n;
for (int i = 2; i <= n; ++i) {
if (isPrime(i)) {
cout << i << endl;
}
}
return 0;
}
这里还会有个数学证明，优化了遍历条件。提高了效率，使其 i < x 化为 i * i <= x。
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
bool isPrime(int x) {
if (x <= 1) return false;
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0 && x != 2) {
return false;
}
}
return true;
}
int main(void) {
int n; cin >> n;
for (int i = 2; i <= n; ++i) {
if (isPrime(i)) {
cout << i << endl;
}
}
return 0;
}
朴素筛的时候，我们就知道用数学所谓的 平方根，因子相关知识进行优化。那么也不难想到，任何数的倍数其实都不可能是质数的！所以我们只需要筛出不是质数的，剩下的就是质数喽。
#include <iostream>
#include <string.h>
using namespace std;
const int maxN = 1e5 + 10;
bool primeArr[maxN];
int main(void) {
int n; cin >> n;
memset(primeArr, true, sizeof(bool) * maxN);
primeArr[0] = false;
primeArr[1] = false;
for (int i = 2; i * i <= n; ++i) {
for (int j = 2 * i; j < n; j += i) {
primeArr[j] = false;
}
}
for (int i = 0; i < n; ++i) {
if (primeArr[i]) {
cout << i << endl;
}
}
return 0;
}
其实朴素筛、埃氏筛 速度已经不错了，但有些时候可能需要最好的性能。此时就需要 使用 欧拉筛，它主要是优化了埃氏筛的缺点。
埃氏筛中，有这样一种情况，会导致多筛！比如 6 = 2 * 3，那么 对于 2 来说会有 * 3 的时候，而对于 3 来说又会有*2 的时候，但其实只需要筛一次就够，如果能保证筛一次的话，时间复杂度就可以 O(n)。
最小质因子。合数，那么就只筛了一次，不会多筛。就比如说 6 只在 最小质因子 2 乘以 3 的时候，才会被标记，其余情况不会被标记。#include <iostream>
#include <string.h>
using namespace std;
const int maxN = 1e5 + 10;
int primes[maxN]; // 升序
bool vis[maxN];
int main(void) {
int n; cin >> n;
memset(vis, false, sizeof(bool) * maxN); // 假设都没被标记为合数
int pos = 0;
for (int i = 2; i <= n; ++i) {
if (!vis[i]) // 先判断是不是合数
{
primes[pos++] = i; // i 是质数
// 当前这个质数 * 其它已经确认的质数 = 合数
for (int j = 0; j < pos && i * primes[j] <= n; ++j) {
vis[i * primes[j]] = true; // 这个是合数
}
} else {
// 当前这个合数 * 已经确认的质数（从最小的开始） = 合数
// 但当前这个合数很可能是 某个最小质数的倍数，所以如果用它继续筛就筛多了
// 必须判断出它是哪个最小质数的倍数
for (int j = 0; j < pos && i * primes[j] <= n; ++j) {
vis[i * primes[j]] = true; // 这个是合数
if (i % primes[j] == 0) {
// 看下当前这个 i 是不是最小质数
break; // 证明不是最小质数了，可以是 primes[j] 的倍数，那么这个 primes[j] 在后续就可以帮他继续筛完
// 即 当前的 i 就不用去做没意义的筛了。
}
}
}
}
for (int i = 0; i < pos; ++i) {
cout << primes[i] << endl;
}
return 0;
}
前缀和：快速求某个区间中所有元素的累加和。（所以这些数肯定是要 反复使用进行累加的）。差分：对多个区间进行加数，快速得到操作后的数组集合（需要学习前缀和）。#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
int main() {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
int p, q; cin >> p >> q;
int sum = 0;
for (int i = p; i <= q; ++i) {
sum += arr[i];
}
cout << sum << endl;
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN];
int sum[maxN] = {0};
int main() {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
sum[1] = arr[0];
for (int i = 2; i <= n; ++i) {
sum[i] = sum[i - 1] + arr[i - 1];
}
// 1 2 3 4 5
// 1 3 6 10 15
for (int i = 0; i < n + 1; ++i) {
cout << sum[i] << " ";
}
int p, q; cin >> p >> q;
cout << endl;
cout << sum[q + 1] - sum[p - 1] << endl;
return 0;
}
核心思想还是 前缀和，只不过是从 一维数组拓展到了二维矩阵。所以我们要探索有哪些变化，总结出通式，解决二维前缀和问题。
#include <iostream>
using namespace std;
const int maxN = 1005;
int arr[maxN][maxN] = {0};
int sum[maxN][maxN] = {0};
int main() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
cout << sum[i][j] << " ";
}
cout << endl;
}
int q; cin >> q;
while (q--) {
int x1, y1, x2, y2; cin >> x1 >> y1; cin >> x2 >> y2;
cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] << endl;
}
return 0;
}
原理：构建差分数组，将其当作新的原数组。然后进行前缀和操作，意外发现由差分数组还原成了真正的原数组。所以，只要我们在差分数组里进行区域内的加数操作，得到普遍规律可循，最后进行前缀和就可以得到我们的目标数组。
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int arr[maxN] = {0};
int d[maxN] = {0};
int main() {
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int i = 1; i <= n; i++) {
d[i] = arr[i] - arr[i - 1];
}
while (q--) {
int l, r, c; cin >> l >> r >> c;
d[l] += c;
if (r + 1 < n) {
d[r + 1] -= c;
}
}
for (int i = 1; i <= n; i++) {
arr[i] = d[i] + arr[i - 1];
cout << arr[i] << " ";
}
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1005;
int arr[maxN][maxN] = {0};
int d[maxN][maxN] = {0}; // 差分数组
int sum[maxN][maxN] = {0}; // 前缀和数组
int main() {
int n, m, q; cin >> n >> m >> q;
// 输入原始数组并初始化差分数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
// 计算差分数组
d[i][j] = arr[i][j] - arr[i - 1][j] - arr[i][j - 1] + arr[i - 1][j - 1];
}
}
// 处理查询
while (q--) {
int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c;
// 更新差分数组
d[x1][y1] += c;
if (y2 + 1 <= m) d[x1][y2 + 1] -= c;
if (x2 + 1 <= n) d[x2 + 1][y1] -= c;
if (x2 + 1 <= n && y2 + 1 <= m) d[x2 + 1][y2 + 1] += c;
}
// 通过差分数组计算前缀和数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = d[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
cout << sum[i][j] << " ";
}
cout << endl;
}
return 0;
}
#include <iostream>
using namespace std;
struct Node {
Node* next;
int data;
};
int main() {
Node* A = new Node();
Node* B = new Node();
A->data = 1;
B->data = 2;
A->next = B;
B->next = NULL;
Node* currentNode = A;
// 1. 遍历
// Node* currentNode = A;
// while (currentNode != NULL) {
// cout << currentNode->data << endl;
// currentNode = currentNode->next;
// }
// 2. 通关下标找到目标节点
// int pos;
// cin >> pos;
// for (int i = 0; i < pos; i++) {
// if (i == 0) {
// currentNode = A;
// } else {
// currentNode = currentNode->next;
// }
// if (currentNode == NULL) {
// break;
// }
// }
// if (currentNode == NULL) cout << A->data << endl;
// else cout << currentNode->data << endl;
// 3. 通过下标删除目标节点
// int pos;
// cin >> pos;
// Node* preNode = A;
// currentNode = preNode->next;
// if (pos == 0) {
// A = currentNode;
// delete preNode;
// } else if (pos > 0) {
// for (int i = 2; i <= pos; i++) {
// preNode = currentNode;
// currentNode = preNode->next;
// if (currentNode == NULL) {
// break;
// }
// }
// if (currentNode == NULL) {cout << "删除失败" << endl;}
// else {
// preNode->next = currentNode->next;
// delete currentNode;
// }
// }
// currentNode = A;
// while (currentNode != NULL) {
// cout << currentNode->data << endl;
// currentNode = currentNode->next;
// }
// 4. 在下标后面插入一个节点
int pos; cin >> pos;
int data; cin >> data;
for (int i = 0; i <= pos; i++) {
if (i == 0) {
currentNode = A;
} else {
currentNode = currentNode->next;
}
if (currentNode == NULL) {
break;
}
}
if (currentNode == NULL) cout << -1 << endl;
else {
Node* newNode = new Node();
newNode->data = data;
newNode->next = currentNode->next;
currentNode->next = newNode;
}
currentNode = A;
while (currentNode != NULL) {
cout << currentNode->data << endl;
currentNode = currentNode->next;
}
return 0;
}
#include <iostream>
using namespace std;
struct Node {
Node* pre;
Node* next;
int data;
};
int main() {
Node* head = new Node();
Node* A = new Node();
Node* B = new Node();
head->next = A;
A->data = 1;
B->data = 2;
A->pre = head;
A->next = B;
B->pre = A;
B->next = NULL;
Node* cNode = head->next;
while (cNode != NULL) {
cout << cNode->data << endl;
cNode = cNode->next;
}
// 删除
int pos; cin >> pos;
int t = pos + 1; // 第 pos + 1 个
cNode = head;
for (int i = 1; i <= t; i++) {
cNode = cNode->next;
if (cNode == NULL) {
cout << "删除失败" << endl;
return 0;
}
}
Node* preNode = cNode->pre;
preNode->next = cNode->next;
delete cNode;
cNode = head->next;
while (cNode != NULL) {
cout << cNode->data << endl;
cNode = cNode->next;
}
return 0;
}
#include <iostream>
using namespace std;
struct Node {
Node* pre;
Node* next;
int data;
};
Node* tail = NULL;
void push(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = NULL;
newNode->pre = tail;
tail->next = newNode;
tail = newNode;
}
int pop() {
Node* preNode = tail->pre;
preNode->next = NULL;
int ret = tail->data;
delete tail;
tail = preNode;
return ret;
}
int main() {
Node* head = new Node();
Node* A = new Node();
Node* B = new Node();
head->next = A;
A->data = 1;
B->data = 2;
A->pre = head;
A->next = B;
B->pre = A;
B->next = NULL;
tail = B;
Node* cNode = head->next;
while (cNode != NULL) {
cout << cNode->data << endl;
cNode = cNode->next;
}
push(3);
push(4);
cNode = head->next;
while (cNode != NULL) {
cout << cNode->data << endl;
cNode = cNode->next;
}
pop();
cNode = head->next;
while (cNode != NULL) {
cout << cNode->data << endl;
cNode = cNode->next;
}
return 0;
}
#include <iostream>
using namespace std;
struct Node {
Node* pre;
Node* next;
int data;
};
Node* tail = NULL;
void push(int data) {
Node* newNode = new Node();
newNode->data = data;
newNode->next = NULL;
newNode->pre = tail;
tail->next = newNode;
tail = newNode;
}
int pop() {
Node* preNode = tail->pre;
preNode->next = NULL;
int ret = tail->data;
delete tail;
tail = preNode;
return ret;
}
Node* head = new Node();
int outQue() {
Node* firstNode = head->next;
if (firstNode == NULL) return -1;
head->next = firstNode->next;
int ret = firstNode->data;
delete firstNode;
return ret;
}
int main() {
Node* A = new Node();
Node* B = new Node();
head->next = A;
A->data = 1;
B->data = 2;
A->pre = head;
A->next = B;
B->pre = A;
B->next = NULL;
tail = B;
Node* cNode = head->next;
while (cNode != NULL) {
cout << cNode->data << endl;
cNode = cNode->next;
}
push(3);
push(4);
cNode = head->next;
while (cNode != NULL) {
cout << cNode->data << endl;
cNode = cNode->next;
}
outQue();
cNode = head->next;
while (cNode != NULL) {
cout << cNode->data << endl;
cNode = cNode->next;
}
return 0;
}
链表既然能够实现栈和队列，那么自然 数组就也可以实现 栈和队列，甚至可以 模拟链表的逻辑。我们来看下。
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int nodeArr[maxN];
int linkArr[maxN];
int main() {
linkArr[0] = 1; // 0 号 指向 1 号节点
nodeArr[1] = 1; // 1 号 节点
nodeArr[2] = 2; // 2 号 节点
linkArr[1] = 2; // 1 号 指向 2 号节点
linkArr[2] = -1; // 定义 -1 是下个节点无 NULL
int nextPos = linkArr[0];
int cNode = nodeArr[nextPos];
while (nextPos != -1) {
cout << cNode << endl;
nextPos = linkArr[cNode];
cNode = nodeArr[nextPos];
}
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int stack[maxN];
int tail = 0; // 当前要入栈位置
void push(int data) {
if (tail >= maxN) {
cout << "满了" << endl;
return;
}
stack[tail++] = data;
}
int pop() {
if (tail == 0) return -1;
return stack[--tail];
}
int main() {
push(1);
push(2);
for (int i = 0; i < tail; ++i) {
cout << stack[i] << endl;
}
pop();
for (int i = 0; i < tail; ++i) {
cout << stack[i] << endl;
}
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int q[maxN];
int top = 0;
int tail = -1;
void push(int x) {
q[++tail] = x;
}
int pop() {
return q[top++];
}
int main() {
push(2);
if (tail < top) {
cout << "空的" << endl;
}
cout << "数量" << tail + 1 - top << endl;
cout << pop() << endl;
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1e5 + 10;
int q[maxN];
int top = 0; // 头元素下标
int tail = 0; // 待插入节点的下标（即队尾的下一个下标）
bool isFull() {
return (tail + 1) % maxN == top;
}
void push(int data) {
if (isFull()) {
cout << "队列满了" << endl;
return;
}
q[tail] = data;
tail = (tail + 1) % maxN;
}
int outQ() {
if (top == tail) {
cout << "队列空的" << endl;
return -1;
}
int ret = q[top];
top = (top + 1) % maxN;
return ret;
}
int main() {
push(1);
push(2);
cout << outQ() << endl;
return 0;
}
讲 DFS 与 BFS 这就不得不说一个典故（迷宫）。
想象一下，你进入了一个巨大的迷宫，你的目标是从起点
S找到终点T。 迷宫的结构如下，其中#代表墙，不能走；.代表路，可以走。
S . . # . . . . # . . . # . . # . . . . . . . # # . . . # . # T . . .
现在有两个问题被提出：
DFS：深度优先搜索，被戏称为一路走到黑。随便选一条路，死磕到底，碰壁后再倒回来换条路去走。
S 开始，开始，你标记'我已经来过这里了'。T。S 压入栈。B）。注意，拿的是最新的那个！B 是不是终点？如果是，胜利！B 周围所有能走且没走过的邻居，按顺序压入栈。#include <iostream>
using namespace std;
// 我们是 节点，二维数组，所以最好是 建立 x,y
// 题目要求我们 用 x,y 下标 去确定一个节点的话，那么我们就要定义 这样的结构
typedef struct {
int x, y;
} Node;
typedef struct {
Node point;
int dir; // 下次探索的方向 0 1 2 3
} SNode;
const int maxN = 105;
Node d[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool vis[maxN][maxN]; // 为走过的节点打标记
Node path[maxN * maxN];
int pathLen = 0;
char arr[maxN][maxN];
SNode s[maxN * maxN];
int top = -1;
int main(void) {
int n, m; cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> arr[i][j];
vis[i][j] = false;
if (arr[i][j] == 'S') {
s[++top] = {i, j, 0};
vis[i][j] = true;
pathLen = 1;
path[0] = {i, j};
}
}
}
while (top >= 0) {
// 只有栈为空的时候，才不去探索
SNode* cNode = &s[top];
if (cNode->dir > 3) {
vis[cNode->point.x][cNode->point.y] = false;
pathLen--;
top--;
continue;
}
int nx = cNode->point.x + d[cNode->dir].x;
int ny = cNode->point.y + d[cNode->dir].y;
cNode->dir++;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && arr[nx][ny] != '#') {
vis[nx][ny] = true;
path[pathLen++] = {nx, ny};
if (arr[nx][ny] == 'T') {
for (int i = 0; i < pathLen; ++i) {
cout << path[i].x << "," << path[i].y << " ";
}
cout << endl;
vis[nx][ny] = false;
pathLen--;
} else {
s[++top] = {nx, ny, 0};
}
}
}
return 0;
}
#include <iostream>
using namespace std;
const int maxN = 1005;
typedef struct {
int x, y;
} Point;
typedef struct {
Point p;
int nextDir; // 下一步尝试的方向 (0~3)
} StackNode;
// 方向：上下左右
Point d[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool vis[maxN][maxN]; // 是否走过了
Point path[maxN];
int pathLen = 0;
int totalPaths = 0; // 记录多少种路径方案
char arr[maxN][maxN];
int n, m;
// 5,7
void dfs(int x, int y) {
vis[x][y] = true;
path[pathLen++] = {x, y};
if (arr[x][y] == 'T') {
printf("Path %d:\n", ++totalPaths);
for (int i = 0; i < pathLen; i++) {
printf("(%d,%d) ", path[i].x, path[i].y);
}
printf("\n\n");
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + d[i].x;
int ny = y + d[i].y;
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && arr[nx][ny] != '#') {
// 没有访问过
dfs(nx, ny);
vis[nx][ny] = false;
pathLen--;
}
}
}
int main(void) {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> arr[i][j];
}
}
int startX = -1, startY = -1; // 从 -1 开始
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (arr[i][j] == 'S') {
startX = i;
startY = j;
break;
}
}
if (startX != -1) break;
}
if (startX == -1) {
printf("没有起始点\n");
return 1;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
vis[i][j] = false;
dfs(startX, startY);
if (totalPaths == 0) {
printf("No path found!\n");
} else {
printf("Total paths: %d\n", totalPaths);
}
return 0;
}
BFS：广度优先搜索，又称为地毯式搜索。先探索所有最近的地方（层次感），再探索更远的地方。
S 开始，你标记'我已经来过这里了'。S，向四周（上、下、左、右）可通行的方向看，把所有能直接到达的点都记录下来。这些是你的'第一层'邻居。T。S 放进队列。A）。A 是不是终点？如果是，胜利！A 周围所有能走且没走过的邻居，按顺序（比如上、下、左、右）依次放入队列的末尾。#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxN = 1005;
struct Point {
int x;
int y;
};
Point q[maxN];
int top = 0;
int tail = 0;
bool ifFull() {
return (tail + 1) % maxN == top;
}
void push(Point data) {
if (ifFull()) {
return;
}
q[tail] = data;
tail = (tail + 1) % maxN;
}
Point outQ() {
if (top == tail) {
cout << "队列空的" << endl;
return {-1, -1};
}
Point ret = q[top];
top = (top + 1) % maxN;
return ret;
}
Point d[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
char arr[maxN][maxN];
bool vis[maxN][maxN];
Point pre[maxN][maxN]; // 记录当前节点的上一个节点
int main() {
int n, m;
int startX, startY;
int endX, endY;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
vis[i][j] = false;
if (arr[i][j] == 'S') {
startX = i;
startY = j;
}
if (arr[i][j] == 'T') {
endX = i;
endY = j;
}
}
}
push({startX, startY});
vis[startX][startY] = true;
pre[startX][startY] = {-1, -1};
bool flag = false; // 默认没找到 T
while (top != tail) {
Point cNode = outQ();
if (cNode.x == endX && cNode.y == endY) {
flag = true;
break;
}
for (int i = 0; i < 4; i++) {
int nx = cNode.x + d[i].x;
int ny = cNode.y + d[i].y;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (arr[nx][ny] == '#' || vis[nx][ny]) continue;
vis[nx][ny] = true;
pre[nx][ny] = cNode;
push({nx, ny});
}
}
if (!flag) {
cout << "根本没终点" << endl;
} else {
vector<Point> path;
int x = endX, y = endY;
while (x != -1 || y != -1) {
path.push_back({x, y});
Point p = pre[x][y];
x = p.x;
y = p.y;
}
reverse(path.begin(), path.end());
cout << endl;
for (int i = 0; i < path.size(); i++) {
cout << path[i].x << " " << path[i].y;
if (i != path.size() - 1) cout << " -> ";
}
}
return 0;
}
贪心思想的核心是：每一步都做出当前看起来'最好'的选择，希望通过局部最优解最终达到全局最优解。
注意：贪心算法并不总能得到全局最优解，但在某些特定问题上，它是有效的，并且效率很高！
问题：假设你有面值为 1 元、5 元、10 元 的硬币，要找给顾客 36 元，要求用最少数量的硬币。
贪心：每次都尽可能用最大面值的硬币就行了。
#include <stdio.h>
int main() {
// 定义硬币面值（按从大到小排序）
int coins[] = {10, 5, 1};
int numCoins = 3; // sizeof(coins) / sizeof(coins[0]); 这个写法是计算数组元素个数的技巧写法
int amount;
printf("请输入要找零的金额（元）: ");
scanf("%d", &amount);
if (amount < 0) {
printf("金额不能为负数！\n");
return 1;
}
int totalCoins = 0;
printf("找零方案：\n");
for (int i = 0; i < numCoins; i++) {
int count = amount / coins[i]; // 当前面值能用多少个
if (count > 0) {
printf("%d元硬币：%d枚\n", coins[i], count);
totalCoins += count;
amount -= coins[i] * count;
}
}
printf("总共需要硬币：%d枚\n", totalCoins);
return 0;
}
问题：有 n 个活动，每个活动有开始时间和结束时间。你一次只能参加一个活动，如何选择最多的活动？
#include <stdio.h>
#include <stdlib.h>
// 定义活动结构体
typedef struct {
int start;
int finish;
int id; // 活动编号（可选，用于输出原始顺序）
} Activity;
// 比较函数：用于 qsort，按结束时间升序排序
int compare(const void* a, const void* b) {
Activity* actA = (Activity*)a;
Activity* actB = (Activity*)b;
return actA->finish - actB->finish;
}
int main() {
int n;
printf("请输入活动数量：");
scanf("%d", &n);
if (n <= 0) {
printf("活动数量必须大于 0。\n");
return 1;
}
Activity activities[n];
printf("请输入每个活动的开始时间和结束时间（格式：start finish）:\n");
for (int i = 0; i < n; i++) {
scanf("%d %d", &activities[i].start, &activities[i].finish);
activities[i].id = i + 1; // 编号从 1 开始
// 简单校验
if (activities[i].start >= activities[i].finish) {
printf("警告：活动%d的开始时间应小于结束时间！\n", i + 1);
}
}
// 按结束时间升序排序
qsort(activities, n, sizeof(Activity), compare);
// 贪心选择
printf("\n最多可参加的活动如下（按结束时间排序）:\n");
int count = 1;
int lastFinish = activities[0].finish;
printf("活动%d: [%d, %d]\n", activities[0].id, activities[0].start, activities[0].finish);
for (int i = 1; i < n; i++) {
if (activities[i].start >= lastFinish) {
printf("活动%d: [%d, %d]\n", activities[i].id, activities[i].start, activities[i].finish);
count++;
lastFinish = activities[i].finish;
}
}
printf("\n最多可参加 %d 个活动。\n", count);
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online