【最大通过数——二分】

题目

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 2e5+10;int n, m, k;
ll a[N], b[N];bool check(int mid)
{for(int i = 0; i <= mid; i++){if(i > n) break;if(mid-i > m) continue;if(a[i] + b[mid-i] <= k) return true;}return false;
}
int main()
{scanf("%d%d%d", &n, &m, &k);for(int i = 1; i <= n; i++){scanf("%d", a+i);a[i] += a[i-1];}for(int i = 1; i <= m; i++){scanf("%d", b+i);b[i] += b[i-1];}int l = 0, r = 1e9;while(l < r){int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}printf("%d", l);
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 2e5 + 10;int n, m, k;
ll a[N], b[N];
int idx1, idx2;
ll ans;struct node
{ll val, cnt;bool operator<(const node &t) const{return val < t.val;}
} cnta[N], cntb[N];
int main()
{scanf("%d%d%d", &n, &m, &k);for (int i = 1; i <= n; i++){scanf("%d", a + i);a[i] += a[i - 1];if (a[i] <= 1e9)cnta[++idx1] = {a[i], i};}for (int i = 1; i <= m; i++){scanf("%d", b + i);b[i] += b[i - 1];if (b[i] <= 1e9)cntb[++idx2] = {b[i], i};}for (int i = 1; i <= idx1; i++){if (cnta[i].val > k)break;int left = k - cnta[i].val;int idx = upper_bound(cntb + 1, cntb + idx2 + 1, (node){left, 0}) - cntb - 1;ans = max(ans, cnta[i].cnt + cntb[idx].cnt);}int idx = upper_bound(cntb + 1, cntb + idx2 + 1, (node){k, 0}) - cntb - 1;ans = max(ans, cntb[idx].cnt);printf("%lld", ans);return 0;
}