题目：最大通过数（蓝桥OJ 3346）

本文主要是介绍题目：最大通过数（蓝桥OJ 3346），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

---

解题思路：

        先枚举a再在内部枚举b找最大，但只是这样肯定会超时。因此内部需要使用二分时间复杂度为logn，具体使用就是找到a情况下的b最大的通过，找到每种a下的最大通过值。a使用前缀和。

---

题解：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
using ll = long long;
ll a[N], b[N];  // 前缀和开LL，可以简化一些步骤int main()
{int n, m, k;cin >> n >> m >> k;for(int i = 1; i <= n; i++){cin >> a[i];a[i] += a[i - 1];  // 简化前缀和写法} for(int i = 1; i <= m; i++){cin >> b[i];b[i] += b[i - 1];} int ans = 0;for(int i = 0; i <= n; i++){if(a[i] > k)break;ll sum = k - a[i]; int x = upper_bound(b, b + m + 1, sum) - b - 1;  // 取第一个大于sum的下标操作。二分时间是lognans = max(ans, i + x);  // max需要有上一次来承接，且是一次变化一次的那种***}cout << ans << '\n';return 0;
}

---

知识点:前缀和，二分函数

这篇关于题目：最大通过数（蓝桥OJ 3346）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---