小和问题(C++实现)
2021/10/9 14:50:42
本文主要是介绍小和问题(C++实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
归并求小和 在数组中求小和,既要排好序,也要求小和
小和:在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和
用归并来实现
例子
[1,3,4,2,5]
1左边比1小的数:没有
3左边比3小的数:1
4左边比4小的数:1,3
2左边比2小的数:1
5左边比5小的数:1,3,4,2
所以小和为1+1+3+1+1+3+4+2=16
代码如下:
#include<iostream> #include<vector> using namespace std; int process(vector<int>& arr, int L, int R); int merge(vector<int>& arr, int L, int M, int R); int smallSum(vector<int>& arr)//小和函数 { if (arr.empty()) { return 0; } return process(arr, 0, arr.size() - 1); } int process(vector<int>& arr, int L, int R) { if (L == R) { return 0; } int mid = L + ((R - L) >> 1); return process(arr, L, mid) + process(arr, mid + 1, R) + merge(arr, L, mid, R); //小和等于左边排好序求小和+右边排好序求小和+merge求小和的结果 } int merge(vector<int>& arr,int L,int M,int R) { vector<int>help;//创建一个辅助数组 help.resize(R - L + 1);//开辟和arr一样的大小 int i = 0, p1 = L, p2 = M + 1, res = 0;//res来接收小和 while (p1 <= M && p2 <= R) { res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;//小和+= help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];//用一个临时数组来排序 } while (p1 <= M)//如果右边临界了,把左边加入到辅助数组中 { help[i++] = arr[p1++]; } while (p2 <= R)//如果左边临界了 把右边加入到辅助数组中,上下只会中一个情况 { help[i++] = arr[p2++]; } for (int k = 0; k < help.size(); k++)//把临时数组倒回原数组 { arr[L + k] = help[k]; } return res;//返回小和 } int main() { //测试 vector<int>v; v.push_back(1); v.push_back(3); v.push_back(4); v.push_back(2); v.push_back(5); cout << smallSum(v) << endl;//输出v数组的小和 for (vector<int>::iterator it = v.begin(); it != v.end(); it++)//输出排好序的数组 { cout << *it << " "; } cout << endl; return 0; }
这篇关于小和问题(C++实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-29document对象教程:新手入门指南
- 2024-09-29端到端的 AWS DevOps 项目:使用 ECR 和 RDS 的 ECS Fargate 的 CI/CD 管道
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享