数组中,假定i<k,若a[i]<a[k]且a[i]右侧没有数组元素大于a[k],则认为a[i]与a[k]构成大小对,求数组中所有大小对之和
1条回答 默认 最新
- CodeBytes 2023-03-05 10:18关注
该回答引用ChatGPT
以下是C++实现,通过一次遍历数组来寻找大小对,时间复杂度为O(n):#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int ans = 0, max_num = a[n-1]; for (int i = n-2; i >= 0; i--) { if (a[i] < max_num) { ans += a[i]; } else { max_num = a[i]; } } cout << ans << endl; return 0; }
这里使用一个变量max_num来记录数组右侧的最大值,如果当前的数小于max_num,则说明它和右侧的最大值构成了一个大小对,将它加入答案中。否则,更新max_num为当前的数。最后返回答案即可。
解决评论 打赏 举报无用 1
悬赏问题
- ¥15 is not in the mmseg::model registry。报错,模型注册表找不到自定义模块。
- ¥15 安装quartus II18.1时弹出此error,怎么解决?
- ¥15 keil官网下载psn序列号在哪
- ¥15 想用adb命令做一个通话软件,播放录音
- ¥30 Pytorch深度学习服务器跑不通问题解决?
- ¥15 部分客户订单定位有误的问题
- ¥15 如何在maya程序中利用python编写领子和褶裥的模型的方法
- ¥15 Bug traq 数据包 大概什么价
- ¥15 在anaconda上pytorch和paddle paddle下载报错
- ¥25 自动填写QQ腾讯文档收集表