实验一：递归与分治

一、快速排序及第k小数

1.1 快速排序

1.1.1 问题分析与算法思路

快速排序的基本思想是：

确定分界点x：$q[1]$、$q[(1+r)/2]$、$q[r]$、随机
调整区间：保证所有小于等于 $x$ 的数在 $x$ 的左区间，大于等于 $x$ 的数在 $x$ 的右区间
递归处理左右两段

调整区间可实现的方法有：

方法1

开额外的数组$a[]$、$b[]$
扫描$q[1:r]$
- 当$q[i]\leq x$时，将 $x$ 插入到 $a[]$
- 当$q[i]\geq x$时，将 $x$ 插入到 $b[]$
分别将 $a[]$、$b[]$ 中的数放在 $q$ 中

方法2

$i,j$ 指针分别指向第一个和末尾一个，并分别向右、向左移动

1.1.2 算法设计与代码

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;						//判边界
    int x = q[l], i = l - 1, j = r + 1;	
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

1.1.3 算法演示

多次测试，算法运行结果均正确，符合题意。

1.2 第k小数

1.2.1 减治法（基于快速排序）

本题是课外思考题Top_k问题的变式。我们找到第k小的数，借用“快速排序”的思想，对整个序列进行划分(取序列第一个元素作为枢轴，也可采用随机法、三数取中法等方法)，并返回划分后的位置，若等于k则得到答案；若大于k，则说明该元素左边的元素都小于k，递归求解该位置前面序列第k小的元素即可；若小于k，则递归求解该位置后面序列第k - count(count为该序列中[l,j]的元素数量，其中j为划分后的元素位置)小的元素即可。由此，每次仅需求解大问题的一个子问题，最后即可得到第k小的数。

int Partition(int a[], int l, int r)
{
	int pivot = a[l];						// 取序列第一个元素为pivot
	int i = l - 1, j = r + 1;
	do
	{
		do { i++; } while (a[i] < pivot);
		do { j--; } while (a[j] > pivot);
		if (i < j)  swap(a[i], a[j]);
	} while (i < j);

	return j;
}

void Top_k(int a[], int l, int r, int k)
{
	if (l >= r) return;
	int j = Partition(a, l, r);
	int count = j - l + 1;					// [l,j]区间共有多少数
	if (count == k)
	{
		return;
	}
	else if(count > k)
	{
		Top_k(a, l, j, k);					// 前半部分第k小的数
	}
	else
	{
		Top_k(a, j + 1, r, k - count);		// 后半部分第k - i小的数
	}
}

1.2.2 冒泡排序

当使用冒泡排序，并进行优化，每次冒泡都是找到序列中第i小的数(i为冒泡的次数)，当i = k时，即可找到序列中第k小的数。

void bubblesort(int a[], int k, int n)
{
	for (int i = 0; i < k; i++)
	{
		for (int j = n - 2; j >= i; j--)		 // j控制每轮需要比较的次数 
		{
			if (a[j + 1] < a[j])				// 不满足升序要求，交换顺序 
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}

1.2.3 堆排序

当使用堆排序，每次弹出最小的一个值，那么找第k小的数只需执行k次弹出操作即可。

void down(int u)
{
    int t = u;			// t为点、左孩子、右孩子三个点中最小的一个点
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)			// 根节点不是最小的
    {
        // 与最小的点交换
        swap(h[u], h[t]);
        down(t);		// 递归处理
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        swap(h[u / 2], h[u]);
        u >>= 1;		// u /= 2换上去
    }
}

void HeapSort(int h[], int k, int n)
{
    for (int i = n / 2; i; i--) down(i);	// O(n)的时间复杂度建堆

    while (m--)
    {
        if(m == 0) printf("%d\n", h[1]);
        h[1] = h[cnt--];
        down(1);
    }
}

1.2.4 算法演示

多次测试，算法运行结果均正确，符合题意。

1.3 算法思考与讨论

我们分析以上算法的时间复杂度：

快速排序的平均时间复杂度为$O(nlogn)$

在第k小数问题中，三种方法的时间复杂度依次是：

减治法：$O(n)$
冒泡排序：$O(k*n)$
堆排序：$O(nlogn)$

减治法时间复杂度推导：

在减治法中，划分算法的时间复杂度为$O(i)$($i$为序列的长度)，则我们有$T(n)=\frac{1}{n} \sum_{i=0}^{n-1}(i+T(i))$，令$T(n + 1)=\frac{1}{n + 1} \sum_{i=0}^{n}(i+T(i))$，得到$(n+1)T(n+1)-nT(n)=T(n)+n+1$，替代法可知$T(n)=n$。

二、棋盘覆盖问题

2.1 问题描述

在一个 $2^k×2^k$ 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的 $4$ 种不同形态的 $L$ 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何 $2$ 个 $L$ 型骨牌不得重叠覆盖。

2.2 问题分析与算法思路

本题可用分治的方式求解。对棋盘的size进行分类：

当 $k=0$ 时，是 $1×1$ 棋盘，棋盘中的骨牌数为 $0$
当 $k >0$ 时，我们将 $2^k×2^k$ 棋盘分割为 $4$ 个 $2^{k-1}×2^{k-1}$ 子棋盘

特殊方格位于 $4$ 个较小子棋盘之一中，而其余 $3$ 个子棋盘中无特殊方格。

我们用一个L型骨牌覆盖这 $3$ 个子棋盘的会合处：

由此，我们对每个子棋盘按照左上，右上，右下，左下的顺时针顺序铺满棋盘；每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。

如果特殊方块在里面，递归下去即可；
如果不在，这根据分割的四个方块的不同位置，把左上角或右上角或左下角或右下角的方格标记为特殊方块，然后继续递归。

每次递归时，子棋盘的size将在原来的基础上减半，并记录骨牌的序号，由此得到结果。

2.3 算法设计与代码

在算法中涉及以下变量，具体意义如下：

$tr$：当前棋盘左上角的行号
$tc$：当前棋盘左上角的列号
$dr$：当前特殊方格所在的行号
$dc$：当前特殊方格所在的列号
$size$：当前棋盘的大小$2^k$

void chessBoard(int tr, int tc, int dr, int dc, int size)
{
    if (size == 1)       // 棋盘方格大小为1,说明递归到最里层  
        return;
    int t = num++;       // 每次递增1  
    int s = size / 2;    // 棋盘中间的行/列号 
    // 检查特殊方块是否在左上角子棋盘中  
    if (dr < tr + s && dc < tc + s)               // 在  
        chessBoard(tr, tc, dr, dc, s);
    else         	// 不在，将该子棋盘右下角的方块视为特殊方块  
    {
        board[tr + s - 1][tc + s - 1] = t;
        chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
    }
    // 检查特殊方块是否在右上角子棋盘中
    if (dr < tr + s && dc >= tc + s)               // 在  
        chessBoard(tr, tc + s, dr, dc, s);
    else            // 不在，将该子棋盘左下角的方块视为特殊方块
    {
        board[tr + s - 1][tc + s] = t;
        chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
    }
    // 检查特殊方块是否在左下角子棋盘中
    if (dr >= tr + s && dc < tc + s)               // 在  
        chessBoard(tr + s, tc, dr, dc, s);
    else            // 不在，将该子棋盘右上角的方块视为特殊方块  
    {
        board[tr + s][tc + s - 1] = t;
        chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
    }
    // 检查特殊方块是否在右下角子棋盘中  
    if (dr >= tr + s && dc >= tc + s)                //在  
        chessBoard(tr + s, tc + s, dr, dc, s);
    else            // 不在，将该子棋盘左上角的方块视为特殊方块  
    {
        board[tr + s][tc + s] = t;
        chessBoard(tr + s, tc + s, tr + s, tc + s, s);
    }
}

2.4 算法演示

算法演示

多次测试，算法运行结果均正确，符合题意。

2.5 算法思考与讨论

我们分析分治算法的时间复杂度：

当 $n=2^k$ 时，$T(n)=\left{\begin{array}{cc}
O(1) & n=1 \
4 T(n / 2)+O(1) & n>1
\end{array}\right.$

由迭代法可知，$T(n)=O(n^{log_2 4})=O(n^2)$

分治即“分而治之”，一个规模很大的问题若要直接求解起来是非常困难的，将一个复杂的问题分解为若干个规模较小但是类似于原问题的子问题，子问题可以再分为更小的子问题，最终达到子问题可以简单的直接求解的目的，那么原问题的解即子问题的解的并集。分治算法可以缩小问题的规模，使得问题的求解变得十分容易。

实验二：动态规划

一、计算矩阵连乘积

1.1 问题描述

在科学计算中经常要计算矩阵的乘积。矩阵 $A$ 和 $B$ 可乘的条件是矩阵 $A$ 的列数等于矩阵 $B$ 的行数。若 $A$ 是一个 $p×q$ 的矩阵，$B$ 是一个 $q×r$ 的矩阵，则其乘积 $C=AB$ 是一个 $p×r$ 的矩阵。

其标准计算公式为：

$C_{i j}=\sum_{k=1}^{q} A_{i k} B_{k j} \quad \text { 其中 } 1 \leq i \leq p, \quad 1 \leq j \leq r$

由该公式知计算 $C=AB$ 总共需要 $pqr$ 次的数乘。

现在的问题是，给定 $n$ 个矩阵 ${A_1,A_2,…,A_n}$。其中 $A_i$ 与 $A_{i+1}$ 是可乘的，$i=1,2,…,n-1$。要求计算出这 $n$ 个矩阵的连乘积$A_1A_2…A_n$。

1.2 问题分析与算法思路

我们设二维数组 $m[N][N]$ 表示当前矩阵的连乘次数，一维数组 $p[N]$ 表示各矩阵的维度（其中 $p[0]$ 表示第一个矩阵的行数，$pi$ 表示第 $i$ 个矩阵的列数），则有以下递归公式：

$m[i][j]=\left{\begin{array}{cc}
0 & i=j \
\min \limits_{i \leq k<j}\left{m[i][k]+m[k+1][j]+p_{i-1} p_{k} p_{j}\right} & i<j
\end{array}\right.$

我们先将 $m$ 数组的对角线初始化为0，然后依次计算第 $i$ 个矩阵与第 $i + r - 1$ 个矩阵到最后一个矩阵连乘的最优解情况；依次在 $r − 1$ 个分隔位置中依次检测最优分隔点：对于每个分隔点，变换一次分隔位置，再进行逐一测试，如果有更优的分隔点，就替换掉当前的分隔点。

由此，我们输出 $m[1][n]$，即得到最少的连乘计算次数；记录间隔位置，则可以输出计算连乘的顺序，即最佳添加括号的方式。

1.3 算法设计与代码

void MatrixChain(int n)
{
	int r, i, j, k;
	for (i = 0; i <= n; i++)				// 初始化对角线
	{
		m[i][i] = 0;
	}
	for (r = 2; r <= n; r++)				// r 个矩阵连乘
	{
		for (i = 1; i <= n - r + 1; i++)	 // 依次计算每r个矩阵相连乘的最优解情况
		{
			j = i + r - 1;
			m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
			s[i][j] = i;					// 分隔位置
			for (k = i + 1; k < j; k++)		 // 变换分隔位置，逐一测试
			{
				int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
				if (t < m[i][j])			// 如果变换后的位置更优，则替换原来的分隔方法
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

void print(int i, int j)		// 输出连乘顺序
{
	if (i == j)
	{
		cout << "p[" << i << "]";
		return;
	}
	cout << "(";
	print(i, s[i][j]);
	print(s[i][j] + 1, j);
	cout << ")";
}

1.4 算法演示

多次测试，算法运行结果均正确，符合题意。

1.5 算法思考与讨论

计算矩阵的连乘积是动态规划中的一个经典问题，通过动态规划计算连乘积的时间复杂度为 $O(n^3)$ ，在需要大规模的矩阵连乘时，选择最优的连乘顺序，可以大幅度减小工作量，提高效率。

二、防卫导弹

2.1 问题描述

一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。

现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：

a) 它是该次测试中第一个被防卫导弹截击的导弹；

b) 它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。

2.2 问题分析与算法思路

本题是经典的最长上升子序列问题，具体到本题即“最长不升子序列问题”。

状态表示 $f(i)$：
- 集合：所有以第 $i$ 个数结尾的不升子序列
- 属性：$Max$
状态计算：集合划分——$f(i)$
- 划分依据：最后一个不同的点
- 以上一个数的位置进行划分( $0$ 表示没有上一个数，序列长度为 $1$ )
- 若 $a_i\leq a_j$，则$f[i] = max(f[j] + 1),j=0,1,2,…,i-1$

我综合了曾经做过的OJ👉1010. 拦截导弹👈的题意，其中还要求输出如果要拦截所有导弹最少要配备多少套这种导弹拦截系统，我们分析以下贪心流程：

从前往后扫描每个数，对于每个数：

情况1：如果现有的子序列的结尾都小于当前数，则创建新子序列
情况2：将当前数放到结尾大于等于它的最小的子序列后面

我们证明贪心算法的正确性：

$A$ 表示贪心算法得到的序列个数，$B$ 表示最优解

由于是最优解，必然存在 $B<=A$ ，接下来证明 $A<=B$，运用调整法：

假设存在一种最优策略，不是按照贪心方案进行阶段决策的，如下图，则最优解序列与贪心法得到的序列不同的数**存在关系 $b\geq a$**，我们可以通过有限次的调整，把最优解调整成贪心解的方案，且不增加子序列个数。

故最优解得到的序列个数小于等于贪心算法得到的序列个数。综上，贪心解即是最优解。

2.3 算法设计与代码

void FindMissileNum(int n)
{
    int res = 0, cnt = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (h[i] <= h[j])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);

        int k = 0;
        // q数组记录开好的子序列结尾的数
        while (k < cnt && q[k] < h[i]) k ++ ;		// q数组将是单调上升的, 注1
        if (k == cnt) q[cnt ++ ] = h[i];
        else q[k] = h[i];
    }

    printf("%d\n", res);
    printf("%d\n", cnt);
}

注：

假设 $q$ 数组原先是单调上升的，有$c\leq a \leq b$，而假设 $x$ 要替换 $a$ 这个位置中，则有$c<x\leq a \leq b$，替换后有$c<x \leq b$，仍是单调上升的。

也即，$q$ 数组成立条件是现有的结尾元素都比当前值 $a[i]$ 小才会创建新的序列，所以 $q$ 排序一定是从小到大的，这样顺序查找就相当于 $\geq a[i]$ 的最小的元素。

2.4 算法演示

本题是Acwing在线题库的1010题：👉1010. 拦截导弹👈，提交结果如下：

2.5 算法思考与讨论

本题是动态规划中一个经典的最长上升子序列问题，时间复杂度为 $O(n^2)$；而Acwing题库中附加需计算的拦截所有导弹最少要配备的系统数运用到了贪心解法，实际上与最长上升子序列问题的贪心解法是一致的：

我们可以存储每种长度的上升子序列的最后一位最小是多少；随着长度的增加，最长上升子序列的最后一位值是严格单调递增的。

证明：不妨设长度为$x$的最长上升子序列最后一位与长度为$x-1$的相同，则长度为$x$的子序列的倒数第二位必然比最后一位小，故找到一个长度为$x-1$的最长上升子序列，使得其最后一位更小，与前提矛盾。

我们找到一个最大的小于$a[i]$的数，如$q[4]$，则$q[5]\geq a[i]$，则$a[i]$无法接到长度大于等于5的上升子序列的后面，因此以$a[i]$结尾的最大上升子序列为5，并将 $q[5]$ 的值更新。最后输出 $len$，即可得到最长的上升子序列。

运用贪心解法，求最长上升子序列的时间复杂度可优化至$O(nlogn)$( $logn$ 为二分查找的时间复杂度)。

代码如下：

int len = 0;				    // q数组中的元素个数
for (int i = 0; i < n; i ++ )	 // 枚举每个数
{
	int l = 0, r = len;
	while (l < r)
	{
		int mid = l + r + 1 >> 1;		// l = mid,故上取整
		if (q[mid] < a[i]) l = mid;
		else r = mid - 1;
	}
	len = max(len, r + 1);		 // r + 1代表接到哪个位置的后面
	q[r + 1] = a[i];			// q[r]是小于a[i]的最后一个数, q[r + 1] >= a[i]
}

三、皇宫看守

3.1 问题描述

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。

请你编程计算帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入数据：输入数据由文件名为 $input.txt$ 的文本文件提供。输入文件中数据表示一棵树，描述如下：

第 $1$ 行 $n$，表示树中结点的数目。

第 $2$ 行至第 $n+1$ 行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号 $i$（$0<i\leq n$），在该宫殿安置侍卫所需的经费 $k$，该边的儿子数 $m$，接下来 $m$ 个数，分别是这个节点的 $m$ 个儿子的标号 $r_1,r_2,…,r_m$。

对于一个 $n$（$0 < n \leq 1500$）个结点的树，结点标号在 $1$ 到 $n$ 之间，且标号不重复。

输出数据：输出到 $output.txt$ 文件中。输出文件仅包含一个数，为所求的最少的经费。

如下图的输入数据示例：

Sample Input

>6 
>1 30 3 2 3 4
>2 16 2 5 6
>3 5 0
>4 4 0
>5 11 0
>6 5 0

Sample Output

>25

3.2 问题分析与算法思路

本题要求图中每个点都被观察到：

父节点放置哨兵，所有子节点都 可放可不放 哨兵
父节点不放哨兵，但是他至少有一个 子节点 放置哨兵，观察住了他
父节点不放哨兵，但父节点的 父节点 放置哨兵观察，则 子节点 可放可不放哨兵

则每个节点有以下三种情况：

被父节点观察（0）
被子节点观察（1）
被自己来观察（2）

状态表示：$f_{i,0/1/2}$

集合：以结点 $i$ 为根节点的子树，在 $i$ 状态为 $j$ 的方案
属性：方案中，放置哨兵的代价最少【最小花费】

状态计算：

在 $i$ 上被父节点观察（0）：

$f_{i, 0} =\sum_{i_{c h}} \min \left(f_{i_{c h}, 1}, f_{i_{c h}, 2}\right)$，其中 $i_{c h} \in{\text { ver } \mid \text { ver } \text { 是 } \mathrm{i} \text { 的子节点 }}$

在 $i$ 上被子节点观察（1） ：

$f_{i, 1}=\min \left(f_{i_{c h}, 2}+\sum_{\text {other } i_{c h}} \min \left(f_{\text {other }} i_{c h}, 1, f_{\text {other } i_{c h}, 2}\right)\right)$，其中 $i_{c h} \in{v e r \mid v e r \text { 是 } \mathrm{i} \text { 的子节点 }} \quad \text { other } i_{c h} \in\left{v e r \mid v e r \text { 是 } \mathrm{i} \text { 的子节点, 且 } v e r \neq i_{c h}\right}$

在 $i$ 上被自己来观察（2） ：

$f_{i, 2}=\sum_{i_{c h}} \min \left{f_{i_{c h}, 0}, f_{i_{c h}, 1}, f_{i_{c h}, 2}\right}+w_{i}$，其中 $i_{c h} \in{v e r \mid v e r \text { 是 } \mathrm{i} \text { 的子节点 }}$

我们先从根节点开始DFS，然后遍历当前节点的所有子节点，递归得到当前节点的$f[u][0],f[u][1],f[u][2]$，

最后对根节点取被子节点观察和被自己观察的方案中代价最小的方案min(f[root][1], f[root][2])即可。

3.3 算法设计与代码

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    f[u][2] = w[u];

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];		// 遍历所有子节点
        dfs(j);
        f[u][0] += min(f[j][1], f[j][2]);
        f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
    }

    f[u][1] = 1e9;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        // f[u][0]为所有子节点的摆放方案代价之和, 减去 min(f[j][1], f[j][2]) 即是除了j节点其余节点的代价之和
        f[u][1] = min(f[u][1], f[j][2] + f[u][0]- min(f[j][1], f[j][2]));
    }
}

3.4 算法演示

本题是Acwing在线题库的1010题：👉1077. 皇宫看守👈，提交结果如下：

3.5 算法思考与讨论

本题是树形DP的典型应用，这种DP方式涉及到了树中父节点、子节点之间的邻接关系，根据不同的条件进行分别讨论，确定状态表示和状态计算的策略，并运用树（图）的DFS/BFS算法求解。只要列出正确的关系表达式，具体代码的设计是不难的。

实验三：贪心算法和随机算法

一、背包问题

1.1 问题描述

有一个背包，背包容量是 $M=150$ 。有 $7$ 个物品，物品可以分割成任意大小。

要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品	A	B	C	D	E	F	G
重量	35	30	60	50	40	10	25
价值	10	40	30	50	35	40	30

1.2 问题分析与算法思路

本题是经典的一类背包问题，我们可以依据以下贪心策略进行求解：

我们按照每个物品单位重量的价值进行排序，然后从最大单位重量价值的物品开始装入背包，当剩余背包容量大于等于该物品的重量时，直接放入，并将该物品的价值加入总价值；否则，获取剩余比例，将该比例的物品放入背包中，并将该比例的价值加入总价值，以此得到的就是总价值最大的方案。

我们很容易证明以上贪心策略的正确性：若某次不按照最大单位重量价值的物品进行放置，所得到的总价值一定不是最大的，则贪心解就是最优解。

1.3 算法设计与代码

struct Obj
{
	int id;			// 物品序号
	int w;			// w为各物品的重量
	int v;			// v为各物品的价值
	float unit;		// 单位重量的价值
	bool operator< (const Obj& W)const
	{
		return unit < W.unit;
	}
}obj[N];

void FindMaxValue(int n, int m)
{
	float value = 0;
	sort(obj, obj + n);			// 按照单位重量的价值对物品进行升序排序
	for (int i = n - 1; i >= 0; i--)
	{
		if (m - obj[i].w >= 0)				// 存在剩余容量
		{
			m -= obj[i].w;					// 去掉这部分的背包容量
			value += obj[i].v;				// 加入这部分的价值
			cout << "装入整个第" << l[obj[i].id] << "个物品" << endl;
			if (m == 0) break;
		}
		else
		{
			float ratio = (float) m / obj[i].w;
			cout << "装入" << ratio * 100 << "%第" << l[obj[i].id] << "个物品" << endl;
			value += ratio * obj[i].v;
			break;
		}
	}
	cout << "装入背包中的物品的总价值最大为" << value << endl;
}

1.4 算法演示

多次测试，算法运行结果均正确，符合题意。

1.5 算法思考与讨论

背包问题主要分为01背包、完全背包、多重背包、分组背包等多种类型，主要通过动态规划算法求解。由于这里物品可以分割成任意大小，故可以通过贪心策略，从最大单位重量价值的物品开始装入背包，使得背包的总价值最大，从而解决该问题，算法时间复杂度主要取决于排序的代价 $O(nlogn)$。

二、照亮的山景

2.1 问题描述

在一片山的上空，高度为 $T$ 处有 $N$ 个处于不同位置的灯泡，如图。如果山的边界上某一点于某灯 $i$ 的连线不经过山的其它点，我们称灯 $i$ 可以照亮该点。开尽量少的灯，使得整个山景都被照亮。山被表示成有 $m$ 个转折点的折线。

提示：照亮整个山景相当于照亮每一个转折点。

为了方便下面的描述，我对本题的输入进行了如下的规范：

第 $1$ 列：一个整数 $M$，代表山棱折线的转折点个数；

第 $2-M+1$列：$X_i,H_i$，依序代表转折点的水平坐标以及垂直海拔高度，所有转折点坐标将以 $X$ 坐标由小到大排列；

第 $M+2$ 列：$N,T$，其中 $N$ 代表灯泡个数，$T$ 代表所有灯泡的高度，该高度必定高于整座山最高转折点的高度；

第 $M+3$ 列：有 $N$ 个整数 $B_1,B_2,…,B_N$，代表 $N$ 个灯泡的水平坐标，且依坐标值由小到大排列。

2.2 问题分析与算法思路

我们有以下性质：

照亮整个山景相当于照亮每一个转折点；
如果两盏灯可以照射到顶点 $i$，则两盏灯之间的所有灯也能照射到顶点 $i$。

我们用结构体变量存储山上的各个转折点的横坐标 $x$，纵坐标 $y$，顶点能被灯照到的左端点和右端点：

首先找到每个顶点能被灯照到的左端点和右端点，可以采用遍历每个灯的做法，计算灯到顶点的直线的斜率 $k$ 和截距 $b$，然后计算该灯到顶点这段距离区间内所有顶点的横坐标投影到该直线的纵坐标是否小于该顶点的纵坐标：

若成立，则认为该灯是无法照射到该顶点的，转而判断下一个灯；
若这段距离区间中所有顶点都存在以上条件，则认为该灯可以照射到该顶点，由该灯在顶点处的左右关系对顶点能被灯照到的左、右端点进行更新，并判断下一个灯。

若判断的灯已经在该顶点的右侧且该灯无法照到该顶点，则根据性质 $2$，无需继续判断后续灯是否能照射到该顶点。

经过上述过程，我们得到了每个顶点被哪些灯照到, 记录到 $l$ 和 $r$ 中，接着根据贪心策略获得开灯最少的数量：

依次计算区间内每个数出现的次数，找出区间中出现次数最多的数，由贪心策略可知，其是我们要找的灯的序号。点亮该灯后，将能照射到的顶点删除，然后对剩余顶点重复上述过程，直到顶点被全部照亮。

若贪心策略不是最优解，我们可以通过换部分灯的开关情况使其变为最优解，且不增加要亮灯的数目，则该贪心策略是正确的。

2.3 算法设计与代码

struct Mou
{
	int x;
	int y;
	int l;				// l 为顶点能被灯照到的左端点
	int r;				// r 为顶点能被灯照到的右端点
};
vector<Mou> mou;

void FindLightRegion(int m, int n, int t)
{
	for (int i = 0; i < m; i++)			// 遍历每个顶点
	{
		for (int j = 0; j < n; j++)		// 遍历每个灯
		{
			bool flag = true;

			if (l[j] != mou[i].x)
			{
				// 计算直线的斜率k和截距b
				float k = (float)(t - mou[i].y) / (l[j] - mou[i].x);
				float b = t - k * l[j];
				int s = i;
				while ((l[j] < mou[i].x && --s && l[j] < mou[s].x)
					|| (l[j] > mou[i].x && ++s && l[j] > mou[s].x))		// 遍历灯到该点区间内的所有点
				{
					if (k * mou[s].x + b < mou[s].y)
					{
						flag = false;
						break;
					}
				}
			}

			if (flag)
			{
				if (mou[i].l == -1)
				{
					mou[i].l = mou[i].r = j;
				}
				else
				{
					mou[i].r++;
				}
			}
			else
			{
				if (l[j] > mou[i].x)
					break;				// 无需继续遍历
			}
		}
	}
}

int FindMinLight(int m, int n, int t)
{
	int res = 0;
	FindLightRegion(m, n, t);	// 得到每个顶点被哪些灯照到, 记录到 l 和 r 中
	while (mou.size() != 0)
	{
		// 统计区间每个数出现的次数
		int max = 0, cishu = 0;
		for (auto t : mou)
		{
			map<int, int> nums;
			for (int i = t.l; i <= t.r; i++)
			{
				nums[i]++;
			}
			// 找出区间中出现次数最多的数
			for (auto num : nums)
			{
				if (num.second > cishu)
				{
					max = num.first;
					cishu = num.second;
				}
			}
		}
		// 将出现次数最多的数设为当前需要的灯, 然后删除所有有关的顶点
		res++;
		for (auto it = mou.begin(); it != mou.end();)
		{
			if (it[0].l <= max && it[0].r >= max)
				it = mou.erase(it);
			else
				++it;
		}
	}
	return res;
}

2.4 算法演示

Sample Input：

Sample Out：

多次测试，算法运行结果均正确，符合题意。

2.5 算法思考与讨论

本题网上的很多策略都是有问题的，如有解法认为只要在两山峰的谷底能被照亮，则两山峰间的每个转折点都能被照亮；有解法认为灯只需落在山峰间各第一个转折点与山峰边界的连线所对应的区间，即可点亮整个区间。以上两种策略显然存在问题，若两山峰间存在陡坡，可以构造相应情况使得上述策略是错误的。

我通过求解每个顶点能被灯照到的左端点和右端点，然后运用贪心策略依次计算区间内每个数出现的次数，找出区间中出现次数最多的数，开相应序号的灯，从而求解开灯最少的数量，算法的时间复杂度是 $O(n^2*m)$。

本题花费我的时间是比较长的，首先难点是设计相应的数据结构，并设计正确的策略求解每个顶点能被灯照到的左端点和右端点；同时，在删除已经被点亮的转折点操作时，我对 $vector$ 中变量删除的操作有一些陌生，通过这次实验巩固了我的一些薄弱知识点，收获很大。

三、搬桌子问题

3.1 问题描述

某教学大楼一层有 $n$ 个教室，从左到右依次编号为 $1,2,…,n$。现在要把一些课桌从某些教室搬到另外一些教室，每张桌子都是从编号较小的教室搬到编号较大的教室，每一趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或往右走搬另一张桌子。

输入数据：先输入 $n$、$m$，然后紧接着 $m$ 行输入这 $m$ 张要搬课桌的起始教室和目标教室；

输出数据：最少需要跑几趟。

3.2 问题分析与算法思路

本题只需将任务按起始教室的编号排序，然后从当前已经遍历到的教室开始找到后面最近的教室开始任务；当当前后面教室已经没有开始任务时，进行新一趟遍历。

我们易知该贪心策略是正确的：若不按此策略进行，我们可以通过改变任务执行的顺序，使得跑的趟数不发生改变，则贪心策略是最优的。

3.3 算法设计与代码

struct Move {
	int start;
	int end;
	bool use;
	bool operator< (const Move& W)const
	{
		return start < W.start;
	}
}mov[N];

int runnum(int n, int m)
{
	sort(mov, mov + m);					// 按照任务起始教室的编号排序
	int res = 0, num = 0, work = 0;		 // res为趟数
	while (work < m)
	{
		int num = 0;		// num为当前到的教室编号
		for (int i = 0; i < m; i++)
		{
			if (mov[i].use == false && mov[i].start >= num)
			{
				mov[i].use = true;
				work++;
				num = mov[i].end;
				if (num == n) break;
			}
		}
		res++;
	}
	return res;
}

3.4 算法演示

Sample Input

Sample Output

多次测试，算法运行结果均正确，符合题意。

3.5 算法思考与讨论

本题是贪心算法的一个典型应用，当每次从当前已经遍历到的教室开始找到后面最近的教室开始任务时，可以让单趟遍历到的教室属于任务范围内的比例最大，从而使得整个算法性能达到最优。

附：源代码

实验一：递归与分治

一、快速排序及第k小数

1.1 快速排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;

void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;						//判边界
	int x = q[l], i = l - 1, j = r + 1;
	while (i < j)
	{
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
	quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

int main()
{
	int a[N], k, n;
	cout << "请输入元素个数与序列:" << endl;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	
	quick_sort(a, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
	}

	cout << endl;
	return 0;
}

1.2 第k小数

减治法（基于快速排序）：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;

int Partition(int a[], int l, int r)
{
	int pivot = a[l];						// 取序列第一个元素为pivot
	int i = l - 1, j = r + 1;
	do
	{
		do { i++; } while (a[i] < pivot);
		do { j--; } while (a[j] > pivot);
		if (i < j)  swap(a[i], a[j]);
	} while (i < j);

	return j;
}

void Top_k(int a[], int l, int r, int k)
{
	if (l >= r) return;
	int j = Partition(a, l, r);
	int count = j - l + 1;					// [l,j]区间共有多少数
	if (count == k)
	{
		return;
	}
	else if(count > k)
	{
		Top_k(a, l, j, k);					//前半部分第k小的数
	}
	else
	{
		Top_k(a, j + 1, r, k - count);		//后半部分第k - i小的数
	}
}

int main()
{
	int a[N], k, n;
	cout << "请输入元素个数与序列:" << endl;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	cout << "请输入要获得的第k小数" << endl;
	cin >> k;
	
	Top_k(a, 0, n - 1, k);
    
	cout << "第" << k << "小数是" << a[k - 1] << endl;
	cout << endl;
	return 0;
}

冒泡排序：

#include<iostream>
using namespace std;
const int N = 20;

void bubblesort(int a[], int k, int n)
{
	for (int i = 0; i < k; i++)
	{
		for (int j = n - 2; j >= i; j--)		 // j控制每轮需要比较的次数 
		{
			if (a[j + 1] < a[j])				// 不满足升序要求，交换顺序 
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}

int main()
{
	int a[N], k, n;
	cout << "请输入元素个数与序列:" << endl;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	cout << "请输入要获得的第k小数" << endl;
	cin >> k;
	bubblesort(a, k, n);
	cout << a[k - 1] << endl;
	return 0;
}

堆排序：

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;

int n, m;
int h[N], cnt;

void down(int u)
{
    int t = u;			// t为点、左孩子、右孩子三个点中最小的一个点
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)			// 根节点不是最小的
    {
        // 与最小的点交换
        swap(h[u], h[t]);
        down(t);		// 递归处理
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        swap(h[u / 2], h[u]);
        u >>= 1;		// u /= 2换上去
    }
}

void HeapSort(int h[], int k, int n)
{
    for (int i = n / 2; i; i--) down(i);	// O(n)的时间复杂度建堆

    while (m--)
    {
        if(m == 0) printf("%d\n", h[1]);
        h[1] = h[cnt--];
        down(1);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    cnt = n;
    HeapSort(h, m, n);
    return 0;
}

二、棋盘覆盖问题

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>  
using namespace std;
int num = 1;                   //L型骨牌的编号(递增)  
int board[100][100];  //棋盘  
/*****************************************************
* tr--当前棋盘左上角的行号
* tc--当前棋盘左上角的列号
* dr--当前特殊方格所在的行号
* dc--当前特殊方格所在的列号
* size：当前棋盘的:2^k
*****************************************************/
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
    if (size == 1)       // 棋盘方格大小为1,说明递归到最里层  
        return;
    int t = num++;       // 每次递增1  
    int s = size / 2;    // 棋盘中间的行、列号(相等的)  
    // 检查特殊方块是否在左上角子棋盘中  
    if (dr < tr + s && dc < tc + s)               // 在  
        chessBoard(tr, tc, dr, dc, s);
    else         // 不在，将该子棋盘右下角的方块视为特殊方块  
    {
        board[tr + s - 1][tc + s - 1] = t;
        chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
    }
    // 检查特殊方块是否在右上角子棋盘中
    if (dr < tr + s && dc >= tc + s)               // 在  
        chessBoard(tr, tc + s, dr, dc, s);
    else            // 不在，将该子棋盘左下角的方块视为特殊方块
    {
        board[tr + s - 1][tc + s] = t;
        chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
    }
    // 检查特殊方块是否在左下角子棋盘中
    if (dr >= tr + s && dc < tc + s)               // 在  
        chessBoard(tr + s, tc, dr, dc, s);
    else            // 不在，将该子棋盘右上角的方块视为特殊方块  
    {
        board[tr + s][tc + s - 1] = t;
        chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
    }
    // 检查特殊方块是否在右下角子棋盘中  
    if (dr >= tr + s && dc >= tc + s)                //在  
        chessBoard(tr + s, tc + s, dr, dc, s);
    else            // 不在，将该子棋盘左上角的方块视为特殊方块  
    {
        board[tr + s][tc + s] = t;
        chessBoard(tr + s, tc + s, tr + s, tc + s, s);
    }
}

int main()
{
    int size;
    cout << "输入棋盘的size(大小必须是2的n次幂): ";
    cin >> size;
    int index_x, index_y;
    cout << "输入特殊方格位置的坐标: ";
    getchar();
    scanf("(%d,%d)", &index_x, &index_y);
    chessBoard(0, 0, index_x - 1, index_y - 1, size);
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
            cout << board[i][j] << "\t";
        cout << endl;
    }
}

实验二：动态规划

一、计算矩阵连乘积

#include<iostream>
using namespace std;
const int N = 100;
int p[N];		// 矩阵规模
int m[N][N];	// 最优解
int s[N][N];

void MatrixChain(int n)
{
	int r, i, j, k;
	for (i = 0; i <= n; i++)				// 初始化对角线
	{
		m[i][i] = 0;
	}
	for (r = 2; r <= n; r++)				// r 个矩阵连乘
	{
		for (i = 1; i <= n - r + 1; i++)	// 依次计算每r个矩阵相连乘的最优解情况
		{
			j = i + r - 1;
			m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
			s[i][j] = i;					// 分隔位置
			for (k = i + 1; k < j; k++)		 // 变换分隔位置，逐一测试
			{
				int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
				if (t < m[i][j])			// 如果变换后的位置更优，则替换原来的分隔方法
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

void print(int i, int j)		// 输出连乘顺序
{
	if (i == j)
	{
		cout << "p[" << i << "]";
		return;
	}
	cout << "(";
	print(i, s[i][j]);
	print(s[i][j] + 1, j);
	cout << ")";
}

int main()
{
	int n;			// n个矩阵
	cout << "请输入矩阵的数目：";
	cin >> n;
	int i, j;
	cout << "请输入各个矩阵的维度(相邻维度只需输入一个即可):";
	for (i = 0; i <= n; i++)
	{
		cin >> p[i];
	}
	MatrixChain(n);
	cout << "最佳添加括号的方式为：";
	print(1, n);
	cout << "\n最小计算量的值为：" << m[1][n] << endl;
	return 0;
}

二、防卫导弹

#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int h[N], f[N], q[N];		// q数组记录开好的子序列结尾的数

void FindMissileNum(int n)
{
    int res = 0, cnt = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if (h[i] <= h[j])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);

        int k = 0;
        while (k < cnt && q[k] < h[i]) k ++ ;		// q数组将是单调上升的, 注1
        if (k == cnt) q[cnt ++ ] = h[i];
        else q[k] = h[i];
    }

    printf("%d\n", res);
    printf("%d\n", cnt);
}

int main()
{
    int n;
    while (cin >> h[n])  n ++ ;	
    FindMissileNum(n);
    return 0;
}

三、皇宫看守

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1510;

int n;
int h[N], w[N], e[N], ne[N], idx;
int f[N][3];
bool st[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    f[u][2] = w[u];

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];		// 遍历所有子节点
        dfs(j);
        f[u][0] += min(f[j][1], f[j][2]);
        f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
    }

    f[u][1] = 1e9;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        // f[u][0]为所有子节点的摆放方案代价之和, 减去 min(f[j][1], f[j][2]) 即是除了j节点其余节点的代价之和
        f[u][1] = min(f[u][1], f[j][2] + f[u][0]- min(f[j][1], f[j][2]));
    }
}

int main()
{
    cin >> n;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int id, cost, cnt;
        cin >> id >> cost >> cnt;
        w[id] = cost;           // 在点上记录花费
        while (cnt -- )
        {
            int ver;
            cin >> ver;
            add(id, ver);
            st[ver] = true;     // 标记不是根节点
        }
    }

    int root = 1;
    while (st[root]) root ++ ;  // 找到根节点

    dfs(root);

    cout << min(f[root][1], f[root][2]) << endl;

    return 0;
}

实验三：贪心算法和随机算法

一、背包问题

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
char l[35] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct Obj
{
	int id;			// 物品序号
	int w;			// w为各物品的重量
	int v;			// v为各物品的价值
	float unit;		// 单位重量的价值
	bool operator< (const Obj& W)const
	{
		return unit < W.unit;
	}
}obj[N];

void FindMaxValue(int n, int m)
{
	float value = 0;
	sort(obj, obj + n);			// 按照单位重量的价值对物品进行升序排序
	for (int i = n - 1; i >= 0; i--)
	{
		if (m - obj[i].w >= 0)				// 存在剩余容量
		{
			m -= obj[i].w;					// 去掉这部分的背包容量
			value += obj[i].v;				// 加入这部分的价值
			cout << "装入整个第" << l[obj[i].id] << "个物品" << endl;
			if (m == 0) break;
		}
		else
		{
			float ratio = (float) m / obj[i].w;
			cout << "装入" << ratio * 100 << "%第" << l[obj[i].id] << "个物品" << endl;
			value += ratio * obj[i].v;
			break;
		}
	}
	cout << "装入背包中的物品的总价值最大为" << value << endl;
}

int main()
{
	int n, m;		// n为物品数, m为背包容量
	cout << "请输入物品数和背包容量:";
	cin >> n >> m;
	cout << "请输入各个物品的重量和价值:\n";
	for (int i = 0; i < n; i++)
	{
		cin >> obj[i].w >> obj[i].v;
		obj[i].id = i;
		obj[i].unit = (float) obj[i].v / obj[i].w;
	}
	FindMaxValue(n, m);
	return 0;
}

二、照亮的山景

#include<iostream>
#include<map>
#include<vector>
using namespace std;
const int N = 20;
int l[N], top[N];		// top[N] 表示山峰的编号
struct Mou
{
	int x;
	int y;
	int l;				// l 为顶点能被灯照到的左端点
	int r;				// r 为顶点能被灯照到的右端点
};
vector<Mou> mou;

void FindLightRegion(int m, int n, int t)
{
	for (int i = 0; i < m; i++)			// 遍历每个顶点
	{
		for (int j = 0; j < n; j++)		// 遍历每个灯
		{
			bool flag = true;

			if (l[j] != mou[i].x)
			{
				// 计算直线的斜率k和截距b
				float k = (float)(t - mou[i].y) / (l[j] - mou[i].x);
				float b = t - k * l[j];
				int s = i;
				while ((l[j] < mou[i].x && --s && l[j] < mou[s].x)
					|| (l[j] > mou[i].x && ++s && l[j] > mou[s].x))		// 遍历灯到该点区间内的所有点
				{
					if (k * mou[s].x + b < mou[s].y)
					{
						flag = false;
						break;
					}
				}
			}

			if (flag)
			{
				if (mou[i].l == -1)
				{
					mou[i].l = mou[i].r = j;
				}
				else
				{
					mou[i].r++;
				}
			}
			else
			{
				if (l[j] > mou[i].x)
					break;				// 无需继续遍历
			}
		}
	}
}

int FindMinLight(int m, int n, int t)
{
	int res = 0;
	FindLightRegion(m, n, t);	// 得到每个顶点被哪些灯照到, 记录到 l 和 r 中
	while (mou.size() != 0)
	{
		// 统计区间每个数出现的次数
		int max = 0, cishu = 0;
		for (auto t : mou)
		{
			map<int, int> nums;
			for (int i = t.l; i <= t.r; i++)
			{
				nums[i]++;
			}
			// 找出区间中出现次数最多的数
			for (auto num : nums)
			{
				if (num.second > cishu)
				{
					max = num.first;
					cishu = num.second;
				}
			}
		}
		// 将出现次数最多的数设为当前需要的灯, 然后删除所有有关的顶点
		res++;
		for (auto it = mou.begin(); it != mou.end();)
		{
			if (it[0].l <= max && it[0].r >= max)
				it = mou.erase(it);
			else
				++it;
		}
	}
	return res;
}

int main()
{
	int m, n, t;			// m为山棱转折点的个数, n为灯泡个数, t为灯泡的高度	
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		mou.push_back({ x,y,-1,-1 });	// 转折点的水平坐标和垂直海拔高度, 并预初始化区间
	}
	cin >> n >> t;
	for (int i = 0; i < n; i++)
	{
		cin >> l[i];
	}
	cout << "开灯最少的数量是" << FindMinLight(m, n, t);
	return 0;
}

三、搬桌子问题

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 20;
struct Move {
	int start;
	int end;
	bool use;
	bool operator< (const Move& W)const
	{
		return start < W.start;
	}
}mov[N];

int runnum(int n, int m)
{
	sort(mov, mov + m);					// 按照任务起始教室的编号排序
	int res = 0, num = 0, work = 0;		// res为趟数
	while (work < m)
	{
		int num = 0;		// num为当前到的教室编号
		for (int i = 0; i < m; i++)
		{
			if (mov[i].use == false && mov[i].start >= num)
			{
				mov[i].use = true;
				work++;
				num = mov[i].end;
				if (num == n) break;
			}
		}
		res++;
	}
	return res;
}

int main()
{
	int n, m;	// n为教室数, m为要搬运的工作数
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> mov[i].start >> mov[i].end;
		mov[i].use = false;
	}
	cout << runnum(n, m) << endl;
	return 0;
}

ShiQuLiZhi

https://www.qqzzss.top/2022/11/27/ds-algorithm/suan-fa-ke-cheng-03-suan-fa-fen-xi-yu-she-ji-shi-yan-bao-gao/

本博客所有文章除特别声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 ShiQuLiZhi !

算法程序设计

网络安全第三次实验

2022-12-05 信息安全专业课程

信息安全网络安全

算法课外思考题1118(团伙数量)

2022-11-20 作业

算法程序设计

算法分析与设计实验报告

实验一：递归与分治

一、快速排序及第k小数

1.1 快速排序

1.1.1 问题分析与算法思路

1.1.2 算法设计与代码

1.1.3 算法演示

1.2 第k小数

1.2.1 减治法（基于快速排序）

1.2.2 冒泡排序

1.2.3 堆排序

1.2.4 算法演示

1.3 算法思考与讨论

二、棋盘覆盖问题

2.1 问题描述

2.2 问题分析与算法思路

2.3 算法设计与代码

2.4 算法演示

2.5 算法思考与讨论

实验二：动态规划

一、计算矩阵连乘积

1.1 问题描述

1.2 问题分析与算法思路

1.3 算法设计与代码

1.4 算法演示

1.5 算法思考与讨论

二、防卫导弹

2.1 问题描述

2.2 问题分析与算法思路

2.3 算法设计与代码

2.4 算法演示

2.5 算法思考与讨论

三、皇宫看守

3.1 问题描述

3.2 问题分析与算法思路

3.3 算法设计与代码

3.4 算法演示

3.5 算法思考与讨论

实验三：贪心算法和随机算法

一、背包问题

1.1 问题描述

1.2 问题分析与算法思路

1.3 算法设计与代码

1.4 算法演示

1.5 算法思考与讨论

二、照亮的山景

2.1 问题描述

2.2 问题分析与算法思路

2.3 算法设计与代码

2.4 算法演示

2.5 算法思考与讨论

三、搬桌子问题

3.1 问题描述

3.2 问题分析与算法思路

3.3 算法设计与代码

3.4 算法演示

3.5 算法思考与讨论

附：源代码

实验一：递归与分治

一、快速排序及第k小数

1.1 快速排序

1.2 第k小数

二、棋盘覆盖问题

实验二：动态规划

一、计算矩阵连乘积

二、防卫导弹

三、皇宫看守

实验三：贪心算法和随机算法

一、背包问题

二、照亮的山景

三、搬桌子问题