1. 开幕式排练

这道题目想明白了挺简单的，其实就是排序，排序完以后我们希望将相近的数字摆到一起，怎么算相近？两个挨着算相近，但是这样首尾差别是最大的，而题目给出的是最大的身高差，这样操作没有意义。

既然需要处理首尾地方，我们首先排序，奇数位置的数字为一组，偶数位置的数字为一组，将这两组首尾相连，一定是最小的身高差。因为，出了连接处，所有的数字都只差了2个位次，首尾处差了1个位次。

无法找到比这个解更优的排队方案了，因此，它就是正确的。

代码如下：

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

int main() {
    int n;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end());
    int maxVal = 0;
    for (int i = 0; i < n; i++) {
        if (i - 2 >= 0) {
            maxVal = max(maxVal, vec[i] - vec[i - 2]);
        }
    }
    maxVal = max(maxVal, (vec[1] - vec[0]));
    maxVal = max(maxVal, vec[vec.size() - 1] - vec[vec.size() - 2]);
    cout << maxVal;
    return 0;
}

2. 最少数字

背包问题，能过100%：

#include<vector>
#include<iostream>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }
    vector<int> dp(M + 1);
    dp[0] = 0;
    for (int i = 1; i <= M; i++) {
        dp[i] = 0x3f3f3f3f;
    }
    for (int i = 0; i < N; i++) {
        for (int j = M; j >= 0; j--) {
            if (j - vec[i] >= 0)
                dp[j] = min(dp[j], dp[j - vec[i]] + 1);
        }
        if(dp[M] == 1) break;
    }
    if (dp[M] == 0x3f3f3f3f)
        cout << "No solution";
    else
        cout << dp[M];
    return 0;
}

最开始没看出来，采用dfs，只能过45%：

#include<iostream>
#include<vector>
using namespace std;
void dfs(int& minNum, int curNum, int curSum, int M, vector<int>& vec, int index) {
    if (curSum == M) {
        if (curNum < minNum) {
            minNum = curNum;
        }
        return;
    }
    if (curSum > M) { // 后边不可能存在解了
        return;
    }
    if (index >= vec.size())return;
    // 要 index 位的数字
    dfs(minNum, curNum + 1, curSum + vec[index], M, vec, index + 1);
    // 不要 index 的数字
    dfs(minNum, curNum, curSum, M, vec, index + 1);
    return;
}
int main() {
    int N, M;
    cin >> N >> M;
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }
    int minVal = 0x3f3f3f3f;
    dfs(minVal, 0, 0, M, vec, 0);
    cout << minVal;
    return 0;
}

排序优化了下，能过63%：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int dfs(int curNum, int curSum, int M, vector<int>& vec, int index) {
    if (curSum == M) {
        return curNum;
    }
    if (curSum > M) { // 后边不可能存在解了
        return -1;
    }
    if (index >= vec.size())return -1;
    int res;
    // 要 index 位的数字
    res = dfs(curNum + 1, curSum + vec[index], M, vec, index + 1);
    if (res != -1) {
        return res;
    }
    // 不要 index 的数字
    res = dfs(curNum, curSum, M, vec, index + 1);
    if (res != -1) {
        return res;
    }
    return -1;
}
int main() {
    int N, M;
    cin >> N >> M;
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }
    sort(vec.begin(), vec.end(), greater<int>());
    // int minVal = 0x3f3f3f3f;
    int minVal = dfs(0, 0, M, vec, 0);
    if (minVal == -1)
        cout << "No solution";
    else
        cout << minVal;
    return 0;
}