该问题涉及以 2*min 大于 max 的方式从整数列表的任意一侧删除元素。
vector arr = {250, 10, 11, 12, 19, 200};res = solve(arr);
我们可以使用暴力方法。我们可以尝试所有可能的满足并找到满足 2*min > max 条件的最长子数组。我们还可以使用动态规划方法来尝试所有可能的过度且不需要的子数组组合。
示例（使用矢量 ADT）
假设我们有一个数组，例如“[250, 10, 11, 12, 19, 200]”。为了获得最佳解决方案，我们需要删除元素 [250, 200] 以形成数组 [10, 11, 12, 19]，其中 min 为 10，max 为 19。因此 2*10 > 19。我们从数组，因此输出打印为 2。
下面是一个 C++ 程序，它描述了如何从数组中删除最小数量的元素，使得最小值的两倍大于最大值 –
立即学习“C++免费学习笔记（深入）”；
#include #include using namespace std;int solve(vector arr) { int startIndex = 0, endIndex = 0; bool foundAnAnswer = false; for (int start=0; start<arr.size(); start++) { int min = INT32_MAX, max = INT32_MIN; for (int end=start; end<arr.size(); end++) { if (arr[end] max) max = arr[end]; if (2*min endIndex - startIndex || !foundAnAnswer) { startIndex = start; endIndex = end; foundAnAnswer = true; } } } if (!foundAnAnswer) return arr.size(); return (arr.size() - (endIndex - startIndex + 1));}int main() { vector arr = {250, 10, 11, 12, 19, 200}; cout << solve(arr); return 0;}
输出
2
示例（不使用矢量 ADT）
下面是一个 C++ 程序，描述如何从数组中删除最小数量的元素，使得最小值的两倍大于最大值，但不使用 Vector ADT –
#include using namespace std;int min(int a, int b) {return (a < b)? a : b;}int min(int arr[], int low, int high) { int minimum = arr[low]; for (int i=low+1; i arr[i]) minimum = arr[i]; return minimum; }int max(int arr[], int low, int high) { int maximum = arr[low]; for (int i=low+1; i<=high; i++) if (maximum = high) return 0; int m1 = min(arr, low, high); int m2 = max(arr, low, high); if (2*m1 > m2) return 0; return min(minimum_removals(arr, low+1, high), minimum_removals(arr, low, high-1)) + 1; }int main() { int arr[] = {12, 45, 32, 88, 100}; int n = sizeof(arr)/sizeof(arr[0]); cout << minimum_removals(arr, 0, n-1); return 0; }
输出
3
结论
这里我们使用暴力方法来查找最长的子数组。其他可能的解决方案可能包括通过重复从两侧弹出元素以及其他方法来检查每个可能的子数组。尽管如此，它们的实施工作量很大，而且优化程度较低。这里的时间复杂度是 O(n^2)，因为我们已经遍历了所有子数组。
以上就是C++程序，从两侧删除最小的元素，使得2*最小值大于最大值的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1443876.html
微信扫一扫 
支付宝扫一扫 
