导语
机试一共三个题。分为两个基础题和一个进阶题。两个基础题各100分，进阶题200分，总计400分。
进阶题 堆积木（200分）
- 有一堆长方体积木,他们的宽度和高度都相同,但长度不一。
- 小橙想把这堆积木叠成一面墙，墙的每层可以放一个积木，也可以将两个积木拼起来，要求每层的长度相同。
- 若必须用完这些积木，叠成的墙最多为多少层？
- 如下是叠成一面墙的图示，积木仅按宽和高所在的面进行拼接。（图这里没法找到）
-
- 输入描述：
- 输入为一行，为各个积木的长度，数字为正整数，并由空格分隔。积木的数量和长度都不超过5000.
- 输出描述：
- 输出一个数字，为强的最大层数，如果无法按要求叠成每层长度一致的墙，则输出-1。
-
- 示例1：
- 输入
- 3 6 6 3
- 输出
- 3
- 说明
- 可以每层都是长度3和6的积木拼接起来，这样每层的长度为9，层数为2；
- 也可以其中两层直接用长度6的积木，两个长度3的积木拼接为一层，这样层数为3，故输出3
-
- 示例2：
- 输入
- 1 4 2 3 6
- 输出
- -1
- 说明
- 无法用这些积木叠成每层长度一致的墙，故输出-1。
思路
感觉这个200的题也没有比100分的题目难。我个人的思路是： 首先搭积木的每一层的长度越小，那么层高就越大。并且层高就能与数组所有元素之和/每一层的长度。
所以我们可以按照每一层积木的长度（layer_length）从小向大进行遍历，判断是否能按照当前层的长度为layer_length搭好积木，如果可以的话，就找到了最优解： sum / layer_length, 否则layer_length ++，继续判断。如果遍历结束都无法满足条件，说明无法用这些积木叠成每层长度一致的墙，故输出-1。
所以问题就被拆分成了更小的问题：如果判断是否能够按照layer_length的长度来搭建好积木呢？假设我们实现一个函数canSum。这个函数的作用是判断在数组中取元素，是否可以组成target，如果可以组成target，就在数组中移除这些元素，并返回true,否则返回false。 有了这个canSum函数，那么就很容一可以判断是否能够按照layer_length的长度来搭建好积木呢。因为我们每一次调用canSum其实就是搭建了一层积木，如果搭建成功，我们继续搭建，直到数组中没有元素了，就说明可以完成搭建，否则说明当前无法按照layer_length进行搭建。 分析至此，问题就很简单了。 剩下一些细节问题会写在代码注释中。
代码
bool canSum(vector<int> &nums, int target, int index) {
if (target == 0)
return true;
if (target < 0)
return false;
int remainder = target;
for (int i = index; i < nums.size(); i++) {
if (canSum(nums, target, i + 1)) {
return true; //不取当前位置上的元素nums[i]
} else if (canSum(nums, target - nums[i], i + 1)) { //取到nums[i]
nums.erase(nums.begin() + i);
return true;
}
}
return false;
}
int main() {
std::vector<int> bricks;
int length;
// 从控制台获取输入数组
while (cin>>length) {
bricks.push_back(length);
if (getchar() == '\n') break;
}
// 获取所有砖块长度和
int sum = 0;
for (int brick : bricks) {
sum += brick;
}
//layer_length从1开始遍历
for (int layer_length = 1; layer_length <=sum; layer_length++) {
//剪枝：如果sum都不是layer_length的整数倍，那么肯定无法拼成的
if (sum % layer_length == 0) {
//核心代码通过循环调用canSum,来判断是否能够以当前layer_length搭成
vector<int> temp = bricks;
while (canSum(temp, layer_length,0)) {
continue;
}
if (temp.empty()) {
//可以搭成，直接返回层的个数。
int target_layers = sum / layer_length;
cout << target_layers << endl;
return target_layers;
}
}
}
//遍历结束都没找到可以搭成的layer_length，说明无法用这些积木叠成每层长度一致的墙，故输出-1
cout << -1;
return -1;
}
基础题一 寻找最后一个匹配子序列的下标（100分）
题目描述忘了，在网上没找到匹配的。自己描述下。
给定两个string类型输入target和source。判断source中存在一个子序列等于target吗？如果存在，返回这个子序列的第一个下标。注意有多个子序列满足的时候返回最大的下标。如果不存在，返回-1。
举个栗子： source = “aebceaebc”, target = “abc”。 那么source中有两个子序列可以满足条件index[0] + index[2] + index[3]组成的abc子序列和index[5] +index[7] +index[8]组成的子序列，那么要返回下标较大的子序列的第一个下标也就是5。
思路
思路的话，遍历source。每一次遍历，就判断source中当前位置开头的字符串是否能够找到一个子序列等于target，如果可以就记录下这个位置。遍历完source后，返回这个位置即可。这个位置的初始值赋值为-1，因为如果遍历完都没找到对应的target的话，说明找不到指定case,所以返回-1。
那么如何判断以当前位置开头的字符串中是否能找到一个子序列等于target呢？ 首先就用两个指针，一个指针指source，一个指target，如果两个值相同，他们同时向后移动，否则就将source向后移动。只要target的指针指向了target最后一个元素的下一个元素，说明所有匹配完成了，找到了对应子串，否则说明没找到。 更多细节写在代码中。（只过了85%）
代码
int main() {
string target;
string source ;
//获取输入字符串
getline(cin, target);
getline(cin, source);
int last_position = -1;
int target_len = target.length();
int source_len = source.length();
for (int i = 0; i <= source_len - target_len; i++) {
int index = 0;
//判断source中以i开头的子串中能否有子序列匹配到target
for (int j = 0; i + j < source_len && index<=target_len; j++) {
if (source[i + j] != target[index]) {
continue;
} else {
index++;
}
}
//匹配完成，更新last_position
if (index == target_len) {
last_position = i;
}
}
cout<< last_position;
}
基础题二 种植白杨树（100分）
题目描述
近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。
一个月后，有M棵胡杨未能成活。
现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？
输入描述
N 总种植数量
M 未成活胡杨数量
M 个空格分隔的数，按编号从小到大排列
K 最多可以补种的数量
其中：
1 <= N <= 100000
1 <= M <= N
0 <= K <= M
输出描述
最多的连续胡杨棵树
思路
没写出来，留空。。
