### OJ常用算法（C语言）
#### 概述
在线判断系统（Online Judge，简称OJ）是一种自动化的评测系统，用于评估用户提交的代码是否正确解决了特定的问题。本篇文章将根据提供的文档概述来深入探讨OJ中常用的几种算法：动态规划、贪心算法、分治策略，并结合C语言进行具体分析。
#### 动态规划
动态规划是一种通过把原问题分解为互相重叠的子问题的方式来求解复杂问题的方法。这种方法特别适合解决具有最优子结构性质的问题，即问题的最优解包含了其子问题的最优解。
**特点**：
- **重叠子问题**：子问题被重复计算多次。
- **最优子结构**：问题的最优解可以通过子问题的最优解来构造。
**示例**：0-1背包问题
假设有一个背包容量为W，有n种物品，第i种物品的重量为w[i]，价值为v[i]。选择一些物品装入背包，使得背包中物品的总价值最大。这个问题可以用动态规划来解决：
```c
#include <stdio.h>
#define MAX 10000
int dp[MAX]; // dp[i]表示背包容量为i时的最大价值
int main() {
int n, W; // n: 物品数量, W: 背包容量
scanf("%d%d", &n, &W);
int w[n], v[n];
for(int i = 0; i < n; i++) {
scanf("%d%d", &w[i], &v[i]);
}
for(int i = 0; i <= W; i++) {
dp[i] = 0;
}
for(int i = 0; i < n; i++) {
for(int j = W; j >= w[i]; j--) { // 从大到小遍历避免覆盖问题
dp[j] = (dp[j] > dp[j - w[i]] + v[i]) ? dp[j] : dp[j - w[i]] + v[i];
}
}
printf("Maximum value is %d\n", dp[W]);
return 0;
}
```
#### 贪心算法
贪心算法是通过在每一步选择局部最优解，来寻求全局最优解的一种算法设计策略。这种方法并不总是能得到全局最优解，但在很多情况下能提供足够好的近似解。
**特点**：
- **局部最优**：每一步都采取当前看来最好的选择。
- **不可回溯**：一旦做了选择就不会更改。
**示例**：活动选择问题
假设有一系列活动，每个活动都有一个开始时间和结束时间，目标是选择尽可能多的活动，使得它们之间不冲突。这可以通过贪心算法来解决：
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int start;
int finish;
} Activity;
int compare(const void *a, const void *b) {
return ((Activity *)a)->finish - ((Activity *)b)->finish;
}
int main() {
int n;
scanf("%d", &n);
Activity activities[n];
for(int i = 0; i < n; i++) {
scanf("%d%d", &activities[i].start, &activities[i].finish);
}
qsort(activities, n, sizeof(Activity), compare);
int count = 1; // 假设第一个活动一定选
int lastSelected = 0;
for(int i = 1; i < n; i++) {
if(activities[i].start >= activities[lastSelected].finish) {
count++;
lastSelected = i;
}
}
printf("Maximum number of selected activities: %d\n", count);
return 0;
}
```
#### 分治策略
分治策略是一种将问题分解成若干个较小的子问题来解决的方法。这些子问题互相独立且与原问题属于同一类型。当子问题足够小到可以直接求解时，便得到最终答案。
**特点**：
- **分解**：将问题分解为子问题。
- **独立**：子问题之间相互独立。
- **合并**：将子问题的解合并成原问题的解。
**示例**：快速排序
快速排序是一种高效的排序算法，它利用分治策略实现：
```c
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
```
#### 总结
以上介绍了几种OJ中常用的算法，包括动态规划、贪心算法和分治策略。每种算法都有其独特的适用场景和特点。理解这些算法的基本原理和应用场景对于提高解决问题的能力至关重要。在实际操作中，还需要考虑各种边界条件和特殊情况，确保代码的健壮性和正确性。希望本文对读者理解和应用这些算法有所帮助。
