得物笔试题目（2023

2024-06-02 05:36| 来源: 网络整理| 查看: 265

1. 开幕式排练

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

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

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

代码如下：

#include #include #include using namespace std; int main() { int n; cin >> n; vector 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 > N >> M; vector vec(N); for (int i = 0; i < N; i++) { cin >> vec[i]; } vector dp(M + 1); dp[0] = 0; for (int i = 1; i = 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 = 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 vec(N); for (int i = 0; i < N; i++) { cin >> vec[i]; } int minVal = 0x3f3f3f3f; dfs(minVal, 0, 0, M, vec, 0); cout 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 vec(N); for (int i = 0; i < N; i++) { cin >> vec[i]; } sort(vec.begin(), vec.end(), greater()); // int minVal = 0x3f3f3f3f; int minVal = dfs(0, 0, M, vec, 0); if (minVal == -1) cout

【本文地址】

公司简介

联系我们