P1047 校门外的树 Noip2005普及组第二题

P1047 校门外的树 是一道IT类问题，这是一道简单的模拟题，题目描述如下：

给定了一段道路的长度和一些树的位置，要求计算出这段道路上没有被树覆盖的长度。具体做法是先将树的位置记录在一个数组中，然后对数组进行排序，从而得到每两棵相邻树之间的空隙长度，将这些空隙长度累加起来即可得到未被覆盖的长度。如果第一棵树的位置不是0，则需要在0和第一棵树之间再计算一段长度。

相关问题

NOIP2008普及组第三题搜索

NOIP2008普及组第三题是搜索题目，题目描述如下：

在一个 4*4 的矩阵中，有 1-8 八个数字，其中有一个空位，可以与相邻的数字交换位置，现在给定一个初始状态和一个目标状态，问最少需要几步才能从初始状态到达目标状态。

输入格式：
输入包含两个 4*4 的矩阵，表示初始状态和目标状态，其中 0 表示空位。

输出格式：
输出一个整数，表示最少需要的步数。

输入样例：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

9 5 1 4
13 10 2 7
14 11 6 8
0 15 12 3

输出样例：
46

这道题可以使用广度优先搜索（BFS）的方法进行求解。

首先将初始状态和目标状态转化为字符串，并记录空位的位置。然后利用队列进行 BFS，每次从队首取出一个状态，枚举空位可以移动到的相邻位置，交换数字，得到新的状态，如果新状态等于目标状态，则返回步数，否则将新状态加入队列中。

代码实现如下：

p1048 [noip2005 普及组] 采药

题目描述

有一个草药园，里面有很多草药，采每一株草药都有一个时间ti和一个价值vi。现在有一个采药人，他要在规定时间内采到总价值最大的草药。采药人采药的速度是一定的，他可以选择任意多株草药采摘。这个草药园有点神秘，同一株草药不能采摘两次，而且采摘草药的时间不能超过规定时间。现在给你草药园中每株草药的采摘时间和价值，请你编一个程序输出采到的草药的最大总价值。

输入输出格式

输入格式：

第一行有两个整数T（1<=T<=100）和M（1<=M<=100）。

接下来的M行每行包括两个在1到100之间的整数，分别表示采摘这株草药的时间和这株草药的价值。

输出格式：

只有一个整数，即采到的草药的最大总价值。

输入输出样例

输入样例#1：

70 3
71 100
69 1
1 2

输出样例#1：

3

输入样例#2：

20 5
5 10
10 10
6 12
8 13
7 11

输出样例#2：

36

说明

在样例#1中，采药人有70个时间单位的时间，他可以选择采第2株和第3株草药，总价值为1+2=3。

在样例#2中，采药人有20个时间单位的时间，他可以选择采第1株、第3株和第4株草药，总价值为10+12+13=35。